Clique covers of H-free graphs

Tung Nguyen, Alex Scott, Paul Seymour, Stéphan Thomassé

Research output: Contribution to journalArticlepeer-review

Abstract

It takes n2/4 cliques to cover all the edges of a complete bipartite graph Kn/2,n/2, but how many cliques does it take to cover all the edges of a graph G if G has no Kt,t induced subgraph? We prove that O(n2−1/(2t)) cliques suffice for every n-vertex graph; 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.

Original languageEnglish (US)
Article number103909
JournalEuropean Journal of Combinatorics
Volume118
DOIs
StatePublished - May 2024

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Clique covers of H-free graphs'. Together they form a unique fingerprint.

Cite this