Edge clique covers in graphs with independence number two.

The edge clique cover number ecc(G) of a graph G is the size of the smallest collection of complete subgraphs whose union covers all edges of G. Chen, Jacobson, Kézdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if G is claw‐free, then ecc(G) is bounded above by its order (denoted n). Recently, Javadi and Hajebi verified this conjecture for claw‐free graphs with an independence number at least three. We study the edge clique cover number of graphs with independence number two, which are necessarily claw‐free. We give the first known proof of a linear bound in n for ecc(G) for such graphs, improving upon the bou nd of O(n4∕3log1∕3 n) due to Javadi, Maleki, and Omoomi. More precisely we prove that ecc(G) is at most the minimum of n+δ(G) and 2n−Ω(nlog n), where δ(G) is the minimum degree of G. In the fractional version of the problem, we improve these upper bounds to 32n. We also verify the conjecture for some specific subfamilies, for example, when the edge packing number with respect to cliques (a lower bound for ecc(G)) equals n, and when G contains no induced subgraph isomorphic to H where H is any fixed graph of order 4. [ABSTRACT FROM AUTHOR]