Orderings of uniquely colorable hypergraphs Original Research Article

For a mixed hypergraph image, where image and image are set systems over the vertex set image, a coloring is a partition of image into ‘color classes’ such that every image meets some class in more than one vertex, and every image has a nonempty intersection with at least two classes. A vertex-order image on image (image) is uniquely colorable if the subhypergraph induced by image has precisely one coloring, for each image (image). We prove that it is NP-complete to decide whether a mixed hypergraph admits a uniquely colorable vertex-order, even if the input is restricted to have just one coloring. On the other hand, via a characterization theorem it can be decided in linear time whether a given color-sequence belongs to a mixed hypergraph in which the uniquely colorable vertex-order is unique.