Hypergraph colorings, commutative algebra, and Grobner bases | Posted on:2014-10-11 | Degree:Ph.D | Type:Dissertation | University:University of Rhode Island | Candidate:Krul, Michael E. M | Full Text:PDF | GTID:1450390008455462 | Subject:Applied Mathematics | Abstract/Summary: | | A uniform hypergraph is properly k-colorable if each vertex is colored by one of k colors and no edge is completely colored by one color. In 2008 Hillar gave a complete characterization of the k-colorability of graphs through algebraic methods. We generalize Hillar's work and give a complete algebraic characterization of the k-colorability of r−uniform hypergraphs. In addition to general k colorability, we provide an alternate characterization for 2-colorability and apply this to some constructions of hypergraphs that are minimally non-2-colorable.;We also provide examples and verification of minimality for non-2-colorable 5- and 6-uniform hypergraphs. As a further application, we give a characterization for a uniform hypergraph to be conflict-free colorable.;Finally, we provide an improvement on the construction introduced by Abbott and Hanson in 1969, and improved upon by Seymour in 1974. | Keywords/Search Tags: | Hypergraph | | Related items |
| |
|