Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3

摘要

A clique of a graph is a maximal set of vertices of size at least 2 that induces a complete graph. A k-clique-colouring of a graph is a colouring of the vertices with at most k colours such that no clique is monochromatic. Defossez proved that the 2-clique-colouring of perfect graphs is a 4-complete problem (Defossez (2009) [4]). We strengthen this result by showing that it is still Sigma(P)(2)-complete for weakly chordal graphs. We then determine a hierarchy of nested subclasses of weakly chordal graphs whereby each graph class is in a distinct complexity class, namely Sigma(P)(2)-complete, NP-complete, and P. We solve an open problem posed by Kratochvil and Tuza to determine the complexity of 2-clique colouring of perfect graphs with all cliques having size at least 3 (Kratochvil and Tuza (2002) [7]), proving that it is a Sigma(P)(2)-complete problem. We then determine a hierarchy of nested subclasses of perfect graphs with all cliques having size at least 3 whereby each graph class is in a distinct complexity class, namely Sigma(P)(2)complete, NP-complete, and P. (C) 2016 Elsevier B.V. All rights reserved.