Clique covers of H-free graphs

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

doi:10.1016/j.ejc.2023.103909

Clique covers of H-free graphs

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

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

Abstract

It takes n²/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(n^2−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 language	American English
Article number	103909
Journal	European Journal of Combinatorics
Volume	118
DOIs	https://doi.org/10.1016/j.ejc.2023.103909
State	Published - May 2024

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.ejc.2023.103909

Cite this

@article{d51a516ccdbb4146b1a25e524e391ce9,

title = "Clique covers of H-free graphs",

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.",

author = "Tung Nguyen and Alex Scott and Paul Seymour and St{\'e}phan Thomass{\'e}",

note = "Publisher Copyright: {\textcopyright} 2023",

year = "2024",

month = may,

doi = "10.1016/j.ejc.2023.103909",

language = "American English",

volume = "118",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Clique covers of H-free graphs

AU - Nguyen, Tung

AU - Scott, Alex

AU - Seymour, Paul

AU - Thomassé, Stéphan

PY - 2024/5

Y1 - 2024/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85181148058&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85181148058&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2023.103909

DO - 10.1016/j.ejc.2023.103909

M3 - Article

SN - 0195-6698

VL - 118

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103909

ER -

Clique covers of H-free graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this