“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16491  


Abstract:  
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. 13, 1726; MR1761707] extended this observation to all quasiline graphs and questioned if the same assertion holds for all clawfree graphs. In this paper, using the celebrated structure theorem of clawfree graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all clawfree graphs with independence number at least three. In particular, we prove that if G is a connected clawfree 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 p^{th} power of the cycle C_{n} , for some positive integer p ≤ ⎣(n−1)/3⎦.
Download TeX format 

back to top 