Coloring mixed hypertrees

A mixed hypergraph is a triple ( V , C , D ) where V is its vertex set and C and D are families of subsets of V , called C -edges and D -edges, respectively. For a proper coloring, we require that each C -edge contains two vertices with the same color and each D -edge contains two vertices with diff...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2006-03, Vol.154 (4), p.660-672
Main Authors: Král’, Daniel, Kratochvíl, Jan, Proskurowski, Andrzej, Voss, Heinz-Jürgen
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph coloring
Graph theory
Hypertrees
Mathematics
Mixed hypergraphs
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A mixed hypergraph is a triple ( V , C , D ) where V is its vertex set and C and D are families of subsets of V , called C -edges and D -edges, respectively. For a proper coloring, we require that each C -edge contains two vertices with the same color and each D -edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all k 's for which there exists a proper coloring using exactly k colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree. We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by k colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2005.05.019