Mixed hypergraphs and other coloring problems

KRÁĽ, Daniel. Mixed hypergraphs and other coloring problems. Discrete Mathematics. AMSTERDAM: Elsevier B. V., 2007, roč. 307, 7-8, s. 923-938. ISSN 0012-365X. Dostupné z: https://doi.org/10.1016/j.disc.2005.11.050.

Základní údaje

Originální název

Mixed hypergraphs and other coloring problems

Autoři

KRÁĽ, Daniel

Vydání

Discrete Mathematics, AMSTERDAM, Elsevier B. V. 2007, 0012-365X

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.377

DOI

https://doi.org/10.1016/j.disc.2005.11.050

UT WoS

000244607600017

Klíčová slova anglicky

mixed hypergraphs; graph coloring models; graph homomorphisms

---

Anotace

V originále

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.