Coloring mixed hypertrees (Q2489959)

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.