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 clique

chromatic 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.