Clique covers of H-free graphs

2022/11/22 by Tung Nguyen, Alex Scott, Nguyen, Tung +5
Mathematics · Computer Science · Social Sciences · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #African history and culture studies

paper · pdf · doi:10.48550/arxiv.2211.12065

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

Related

• Clique covers and decompositions of cliques of graphs
• Solving the clique cover problem on (bull, C₄)-free graphs
• Edge Clique Covers in Graphs with Independence Number Two: a Special Case
• On Clique Coverings of Complete Multipartite Graphs
• Maximizing the number of vertices of an N-clique cover of the edges of a\n graph on N vertices