COMPUTER SCIENCE COLLOQUIUM

Unique colorings of mixed hypergraphs

Zsolt Tuza Department of Computer Science, University of Veszprem Computer and Automation Institute, Hungarian Academy of Sciences

Friday, November 26, 2004, at 12:15 Seminar Room

ABSTRACT

In a mixed hypergraph, there are two types of edges, called C-edges and D-edges. In a proper coloring, each C-edge contains two vertices with a common color, and each D-edge has two vertices of distinct colors. (Some mixed hypergraphs do not have any proper coloring.)

A mixed hypergraph is uniquely colorable if it admits a unique partition into color classes; and a permutation of its vertices is a uniquely colorable vertex-order if each of its starting segments induces a uniquely colorable subhypergraph.

The recognition problem of colorable mixed hypergraphs has been known to be NP-complete. Moreover, given a colorable hypergraph H with a proper coloring, it is co-NP-complete to decide whether H is uniquely colorable. We prove:

1. It is NP-complete to recognize mixed hypergraphs admitting a uniquely colorable vertex-order, even if the input is restricted to mixed hypergraphs that are uniquely colorable.
2. For mixed hypergraphs admitting precisely one uniquely colorable vertex-order (apart from the inversion of the first two vertices), the corresponding color sequences can be recognized in linear time, by an easy-to-test necessary and sufficient condition.

This is joint work with Cs. Bujtas.

Host: Bjarne Toft

---

SDU HOME | IMADA HOME | Previous Page

---

Last modified: November 22, 2004.

Joan Boyar (joan@imada.sdu.dk)