We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Edge clique covers in graphs with independence number two.
- Authors
Charbit, Pierre; Hahn, Geňa; Kamiński, Marcin; Lafond, Manuel; Lichiardopol, Nicolas; Naserasr, Reza; Seamone, Ben; Sherkati, Rezvan
- Abstract
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.
- Subjects
RAMSEY numbers; EDGES (Geometry); INTERSECTION numbers; INDEPENDENCE (Mathematics); SUBGRAPHS
- Publication
Journal of Graph Theory, 2021, Vol 97, Issue 2, p324
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22657