University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    •   DRUM
    • Theses and Dissertations from UMD
    • UMD Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Grobner Bases with Applications in Graph Theory

    Thumbnail
    View/Open
    umi-umd-4013.pdf (193.1Kb)
    No. of downloads: 3009

    Date
    2006-12-07
    Author
    Hennessy, Angela
    Advisor
    Washington, Lawrence
    Metadata
    Show full item record
    Abstract
    Grobner 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.
    URI
    http://hdl.handle.net/1903/4203
    Collections
    • Mathematics Theses and Dissertations
    • UMD Theses and Dissertations

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility