Informace o publikaci
Mixed hypergraphs and other coloring problems
| Autoři | |
|---|---|
| Rok publikování | 2007 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Discrete Mathematics |
| Citace | |
| Doi | http://dx.doi.org/10.1016/j.disc.2005.11.050 |
| Klíčová slova | mixed hypergraphs; graph coloring models; graph homomorphisms |
| Popis | 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. |