Uniquely colorable mixed hypergraphs

A mixed hypergraph consists of two families of edges: the \({\mathcal C}\)-edges and \({\mathcal D}\)-edges. In a coloring, every \({\mathcal C}\)-edge has at least two vertices of the same color, while every \({\mathcal D}\)-edge has at least two vertices colored differently. The largest and smallest possible numbers of colors in a coloring are termed the upper and lower chromatic number, \(\overline{\chi}\) and \(\chi \), respectively. A mixed hypergraph is called uniquely colorable if it has precisely one coloring apart from the permutation of colors. In this paper it is shown that every colorable mixed hypergraph can be embedded into some uniquely colorable mixed hypergraph; the role of uniquely colorable subhypergraphs being separators is investigated, recursive operations (orderings and subset contractions) and unique colorings are studied, and it is proved that it is NP-hard to decide whether a mixed hypergraph is uniquely colorable. Also the weaker property where the mixed hypergraph has a unique coloring with \(\overline {\chi}\) colors and a unique coloring with \(\chi \) colors, where \(\overline {\chi}>\chi \) is discussed. Note that the class of these ``weakly uniquely colorable mixed hypergraphs contains all uniquely colorable graphs in the usual sense.

Recommendations

Cited in

(18)

This page was built for publication: Uniquely colorable mixed hypergraphs

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