TY - JOUR
T1 - Clique covers of H-free graphs
AU - Nguyen, Tung
AU - Scott, Alex
AU - Seymour, Paul
AU - Thomassé, Stéphan
N1 - Publisher Copyright:
© 2023
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
AN - SCOPUS:85181148058
SN - 0195-6698
VL - 118
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103909
ER -