Edge clique covers in graphs with independence number two
| Autor: | Rezvan Sherkati, Manuel Lafond, Ben Seamone, Marcin Kamiński, Nicolas Lichiardopol, Geňa Hahn, Pierre Charbit, Reza Naserasr |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Conjecture
010102 general mathematics Induced subgraph 0102 computer and information sciences 01 natural sciences Upper and lower bounds Graph Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Geometry and Topology 0101 mathematics Time complexity Clique cover Independence number Mathematics |
| Zdroj: | Journal of Graph Theory. 97:324-339 |
| ISSN: | 1097-0118 0364-9024 |
| DOI: | 10.1002/jgt.22657 |
| Popis: | The edge clique cover number ecc(G) of a graph G is size of the smallest collection of complete sub-graphs whose union covers all edges of G. Chen, Jacobson, Kezdy, 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 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 bound of O (n 4/3 log 1/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 − Ω (n log n), where δ (G) is the minimum degree of G. In the fractional version of the problem, we improve these upper bounds to 3 2 n. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |