کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420056 | 683891 | 2007 | 13 صفحه PDF | دانلود رایگان |
For a mixed hypergraph H=(X,C,D)H=(X,C,D), where CC and DD are set systems over the vertex set XX, a coloring is a partition of XX into ‘color classes’ such that every C∈CC∈C meets some class in more than one vertex, and every D∈DD∈D has a nonempty intersection with at least two classes. A vertex-order x1,x2,…,xnx1,x2,…,xn on XX (n=|X|n=|X|) is uniquely colorable if the subhypergraph induced by {xj:1⩽j⩽i}{xj:1⩽j⩽i} has precisely one coloring, for each ii (1⩽i⩽n1⩽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.
Journal: Discrete Applied Mathematics - Volume 155, Issue 11, 1 June 2007, Pages 1395–1407