Coloring mixed hypertrees

DOI10.1016/J.DAM.2005.05.019MaRDI QIDQ2489959zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Daniel Král', Jan Kratochvíl, Andrzej Proskurowski, Heinz-Juergen Voss

Publication date 28 April 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.019

graph coloring hypertrees mixed hypergraphs

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10)

Review text

A mixed hypergraph \(H\) is a triple \((V, C, D)\) where \(V\) is the vertex set of \(H\), and \(C\) is a set of subsets of \(V\) (the set of \(C\)-edges of \(H\)) and \(D\) is another set of subsets of \(V\) (the set of \(D\)-edges of \(H\)). Thus, \(H = (V, C, D)\) is a mixed hypergraph means simply that \((V, C)\) and \((V, D)\) are hypergraphs on the same vertex set \(V\). A coloring of the vertices of \(H\) is proper if each \(C\)-edge of \(H\) contains at least two vertices of a common color and each \(D\)-edge of \(H\) contains at least two vertices of different colors. A strict \(k\)-coloring of \(H\) is a proper coloring using exacly \(k\) colors. The feasible set \(F(H)\) of \(H\) consists of all integers \(k\) such that \(H\) admits a strict \(k\)-coloring. The (lower) chromatic number \(\chi(H)\) is the smallest number in \(F(H)\). A mixed hypergraph \((V, C, D)\) is a mixed hypertree if the hypergraph \((V, C\cup D)\) is a hypertree, i.e, there exists a tree \(T\) (an underlying tree) with the same vertex set \(V\) and such that each edge in \(C\cup D\) induces a (connected) subtree in \(T\). Among other results concerning strict coloring on mixed hypertrees, the authors prove that (1) if a mixed hypertree precolored with \(k\geq 1\) colors has a precoloring extension using at least \(k+2\) colors, then it has a precoloring extension with exacly \(k+2\) colors, and it follows from this fact that the feasible set of any mixed hypertree is an interval of integers, (2) the decision if a mixed hypertree \(H = (V, C, D)\) is strict \(k\)-colorable is NP-complete, even in the cases (i) \(C=D\) and each pair of vertices is conteined in at most \(12\) edges, (ii) \(D=\emptyset\) and \(H\) is given together with an underlying tree of maximum degree at most \(3\), (iii) \(C=D\) and \(H\) is given together with an underlying tree of maximum degree at most \(3\), (3) the decision if a mixed hypertree is strict \(k\)-colorable can be solved in polynomial time if the underlying tree is of bounded degree, and (4) if \(k\) is fixed, then the decision if a mixed hypertree without \(D\)-edges is strict \(k\)-colorable can be solved in polynomial time.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Coloring mixed hypertrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489959)