“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16491
School of Mathematics
  Title:   Edge clique cover of claw‐free graphs
  Author(s):  Ramin Javadi (Joint with S. Hajebi)
  Status:   Published
  Journal: J. Graph Theory
  Vol.:  90
  Year:  2019
  Pages:   311-405
  Supported by:  IPM
The smallest number of cliques, covering all edges of a graph G , is called the (edge) clique cover number of G and is denoted by \cc(G) . It is an easy observation that if G is a line graph on n vertices, then \cc(G) ≤ n . 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 G is a connected claw-free graph on n vertices with three pairwise nonadjacent vertices, then \cc(G) ≤ n and the equality holds if and only if G is either the graph of icosahedron, or the complement of a graph on 10 vertices called "twister" or the pth power of the cycle Cn , for some positive integer p ≤ ⎣(n−1)/3⎦.

Download TeX format
back to top
scroll left or right