Show simple item record

dc.contributor.advisorWashington, Lawrenceen_US
dc.contributor.authorHennessy, Angelaen_US
dc.date.accessioned2007-02-01T20:23:32Z
dc.date.available2007-02-01T20:23:32Z
dc.date.issued2006-12-07en_US
dc.identifier.urihttp://hdl.handle.net/1903/4203
dc.description.abstractGrobner basis theory has been applied to the problem of graph coloring with novel results. A graph on n vertices is represented by a polynomial in n variables with degree equal to the number of edges in the graph. In the polynomial ring in n variables, the question of k-colorability is equivalent to determining if the polynomial which represents the graph is contained in a specific ideal. By finding a Grobner basis for this ideal, the problem becomes greatly simplified. We review two different approaches used to solve this problem, and demonstrate the techniques with examples. We also give an algebraic characterization of the Grobner basis of a particular ideal when there is a single k-coloring of a graph.en_US
dc.format.extent197748 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.titleGrobner Bases with Applications in Graph Theoryen_US
dc.typeThesisen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentMathematicsen_US
dc.subject.pqcontrolledMathematicsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record