Hajebi's conjecture on subquadratic clique covers of K_{t,t}-free graphs
Hajebi's conjecture on subquadratic clique covers of K_{t,t}-free graphs
Let be an integer. A graph is -free if it has no induced copy of the complete bipartite graph , and a clique cover is a collection of cliques covering every edge.
Hajebi's conjecture. For every integer , there exists such that every -free graph has a clique cover of size
The conjecture is attributed to Sepehr Hajebi, who proposed it at a conference in Lyon. The paper proves a related bound with , so the proposed statement is solved by the result described in the source.
Sources & referencesView supporting material
Primary source
Tung Nguyen, Alex Scott, Paul Seymour and Stephan Thomasse, “Clique covers of H-free graphs”, arXiv:2211.12065 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.