CLIQUE-CHROMATIC NUMBERS OF CLAW-FREE GRAPHS

Abstract

The clique-chromatic number of a graph is the least number of colors on the vertices of the graph so that no maximal clique of size at least two is monochromatic. A well-known result proved by Gravier et al. in 2003 suggests that the family of claw-free graphs has no bounded cliquechromatic number. Basco et al. explored more in 2004 that the family of claw-free graphs without odd holes has a bounded clique-chromatic number, in particular, these graphs are 2-clique-colorable. In this paper, we study some other subclasses of the family of claw-free graphs with a bounded clique-chromatic number, namely, claw-free graphs without an induced paw and claw-free graphs without an induced diamond.