Premium
Clique‐coloring some classes of odd‐hole‐free graphs
Author(s) -
Défossez David
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20177
Subject(s) - combinatorics , mathematics , split graph , chordal graph , perfect graph , graph coloring , clique number , cograph , discrete mathematics , block graph , clique sum , brooks' theorem , graph , clique graph , line graph , pathwidth , 1 planar graph , graph power
We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C ‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K 4 ‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006