Mixed hypergraphs and other coloring problems

KRÁĽ, Daniel. Mixed hypergraphs and other coloring problems. Discrete Mathematics. AMSTERDAM: Elsevier B. V., 2007, vol. 307, 7-8, p. 923-938. ISSN 0012-365X. Available from: https://doi.org/10.1016/j.disc.2005.11.050.

Basic information

Original name

Mixed hypergraphs and other coloring problems

Authors

KRÁĽ, Daniel

Edition

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

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

Impact factor

Impact factor: 0.377

DOI

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

UT WoS

000244607600017

Keywords in English

mixed hypergraphs; graph coloring models; graph homomorphisms

---

Abstract

In the original language

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.