Clique covers of H-free graphs

DOI10.1016/J.EJC.2023.103909arXiv2211.12065OpenAlexW4390363315MaRDI QIDQ6201890FDOQ6201890

Authors:

Publication date: 26 March 2024

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: It takes $n^2/4$ cliques to cover all the edges of a complete bipartite graph $K_{n/2,n/2}$, but how many cliques does it take to cover all the edges of a graph $G$ if $G$ has no $K_{t,t}$ induced subgraph? We prove that $O(|G{|}^{2-1/(2t)})$ cliques suffice; and also prove that, even for graphs with no stable set of size four, we may need more than linearly many cliques. This settles two questions discussed at a recent conference in Lyon.

Full work available at URL: https://arxiv.org/abs/2211.12065

Recommendations

• Covering the cliques of a graph with vertices
• scientific article; zbMATH DE number 3762108
• Clique covering of graphs
• Regarding two conjectures on clique and biclique partitions
• scientific article; zbMATH DE number 1286502

zbMATH Keywords

induced subgraphcomplete bipartite graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A note on Ramsey numbers
• Asymptotic lower bounds for Ramsey functions
• Ramsey-type theorems
• Edge clique cover of claw-free graphs

This page was built for publication: Clique covers of \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201890)