Edge clique cover of claw‐free graphs
Ramin Javadi, Sepehr Hajebi · Journal of Graph Theory · 2018
Abstract The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi‐line graphs and questioned if the same assertion holds for all claw‐free graphs. In this paper, using the celebrated structure theorem of claw‐free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw‐free graphs with independence number at least three. In particular, we prove that if is a connected claw‐free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer .