Orderings of uniquely colorable hypergraphs ?
For a mixed hypergraph H=(X,C,D) H = ( X , C , D ) , where C C and D D are set systems over the vertex set X X , a coloring  is a partition of X X into color classes such that every C?C C ? C meets some class in more than one vertex, and every D?D D ? D has a nonempty intersection with at least two classes. A vertex-order x1,x2,,xn x 1 , x 2 ,  , x n on X X (n=|X| n = | X | ) is uniquely colorable  if the subhypergraph induced by {xj:1?j?i} { x j : 1 ? j ? i } has precisely one coloring, for each i i (1?i?n 1 ? i ? n ). 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.
mixed hypergraph vertex-order algorithmic complexity uniquely colourable