Circular and uniquely colorable mixed hypergraphs (Q2731368)

A mixed hypergraph is a triple \(H= (X,{\mathcal C},{\mathcal D})\) where \(X\) is the vertex set, and each of \({\mathcal C}\), \({\mathcal D}\) is a family of subsets of \(X\), the \({\mathcal C}\)- and \({\mathcal D}\)-edges, respectively. A proper \(k\)-coloring of a mixed hypergraph is a mapping from the vertex set \(X\) to a set of \(k\) colors such that each \({\mathcal C}\)-edge has two vertices with the same color, and each \({\mathcal D}\)-edge has two vertices with distinct colors. A mixed hypergraph is \(k\)-colorable (uncolorable; uniquely colorable) if it has a proper coloring with at most \(k\) colors (admits no coloring; admits precisely one coloring apart from the permutation of colors). The minimum (maximum) number of colors in a strict coloring of \(H\) is called the lower (upper) chromatic number. A mixed hypergraph \(H= (X,{\mathcal C},{\mathcal D})\) is called circular if there is a cyclic ordering of \(X\) such that every \({\mathcal C}\)- and every \({\mathcal D}\)-edge induces an interval in this ordering.NEWLINENEWLINENEWLINEThe paper studies circular mixed hypergraphs, gives a criterion for uncolorable circular mixed hypergraphs, and shows a bound for the lower chromatic number of colorable circular mixed hypergraphs. Moreover, it gives some criteria for unique colorability of mixed hypergraphs.