×

From graph coloring to constraint satisfaction: there and back again. (English) Zbl 1116.05028

Klazar, Martin (ed.) et al., Topics in discrete mathematics. Dedicated to Jarik Nešetřil on the occasion of his 60th birthday. Berlin: Springer (ISBN 3-540-33698-2/hbk). Algorithms and Combinatorics 26, 407-432 (2006).
Graph colorings may be viewed as special constraint satisfaction problems. The class of \(k\)-coloring problems enjoys a well-known dichotomy of complexity – these problems are polynomial time solvable when \(k\leq \) 2, and NP-complete when \(k\geq \) 3. For general constraint satisfaction problems such dichotomy was conjectured by Feder and Vardi, but has still not been proved in full generality. Results and techniques related to this dichotomy conjecture are discussed. A new concept of ‘fullness’ is introduced to clarify the complexity of constraint satisfaction problems and their dichotomy. Full constraint satisfaction problems may then be specialized back to graph colorings, yielding an interesting novel class of problems in graph theory, related to the study of graph perfection.
For the entire collection see [Zbl 1097.05001].

MSC:

05C15 Coloring of graphs and hypergraphs
05C17 Perfect graphs
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite