Publication details
Mixed hypergraphs and other coloring problems
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Periodical |
| Magazine / Source | Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.disc.2005.11.050 |
| Keywords | mixed hypergraphs; graph coloring models; graph homomorphisms |
| Description | A mixed hypergraph is a triple (V, l, D) where V is the vertex set and l and D are families of subsets of V called l-edges and D-edges, respectively. A proper coloring of a mixed hypergraph (V, l, D) is a coloring of its vertices such that no l-edge is polychromatic and no D-edge is monochromatic. We show that mixed hypergraphs can be used to efficiently model several graph coloring problems including homomorphisms of simple graphs and multigraphs, circular colorings, (H, C, <= K)-colorings, (H, C, K)-colorings, locally surjective, locally bijective and locally injective homomorphisms, L(p, q)-labelings, the channel assignment problem, T-colorings and generalized T-colorings. (c) 2006 Elsevier B.V. All rights reserved. |