Voloshin's conjecture for C-perfect hypertrees.
Csilla Bujtás, Źsolt Tuza · 2010
In the “mixed hypergraph” model, proper coloring requires that vertex subsets of one type (called C-edges) should contain two vertices of the same color, while the other type (D-edges) should not be monochromatic. Voloshin [Australas. J. Combin. 11 (1995), 25–45] introduced the concept of C-perfectness, which can be viewed as a dual kind of graph perfectness in the classical sense, and proposed a characterization for C-perfect hypertrees without D-edges. (A hypergraph is called a hypertree if there exists a graph T which is a tree such that each hyperedge induces a subtree in T.) We prove that the structural characterization conjectured by Voloshin is valid indeed, and it can even be extended in a natural way to mixed hypertrees without (or, with only few) D-edges of size 2; but not to mixed hypertrees in general. The proof is constructive and leads to a fast coloring algorithm, too. In sharp contrast to perfect graphs which can be recognized in polynomial time, the recognition problem of C-perfect hypergraphs is pointed out to be co-NP-complete already on the class of C-hypertrees.