Orderings of uniquely colorable hypergraphs |
| |
Authors: | Csilla Bujtás |
| |
Institution: | Department of Computer Science, University of Pannonia, H-8200 Veszprém, Egyetem u. 10, Hungary |
| |
Abstract: | For a mixed hypergraph H=(X,C,D), where C and D are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every C∈C meets some class in more than one vertex, and every D∈D has a nonempty intersection with at least two classes. A vertex-orderx1,x2,…,xn on X (n=|X|) is uniquely colorable if the subhypergraph induced by {xj:1?j?i} has precisely one coloring, for each i (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. |
| |
Keywords: | Algorithmic complexity Mixed hypergraph Uniquely colourable Vertex-order |
本文献已被 ScienceDirect 等数据库收录! |
|