Type: Article
Publication Date: 2021-01-21
Citations: 3
DOI: https://doi.org/10.1002/jgt.22657
Abstract The edge clique cover number of a graph is the size of the smallest collection of complete subgraphs whose union covers all edges of . Chen, Jacobson, Kézdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if is claw‐free, then is bounded above by its order (denoted ). 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 for for such graphs, improving upon the bou nd of due to Javadi, Maleki, and Omoomi. More precisely we prove that is at most the minimum of and , where is the minimum degree of . In the fractional version of the problem, we improve these upper bounds to . We also verify the conjecture for some specific subfamilies, for example, when the edge packing number with respect to cliques (a lower bound for ) equals , and when contains no induced subgraph isomorphic to where is any fixed graph of order 4.
| Action | Title | Year | Authors |
|---|---|---|---|
| + | An overview of graph covering and partitioning | 2022 |
Stephan Schwartz |