Hajebi's conjecture on subquadratic clique covers of K_{t,t}-free graphs

Let t1t\ge 1 be an integer. A graph is Kt,tK_{t,t}-free if it has no induced copy of the complete bipartite graph Kt,tK_{t,t}, and a clique cover is a collection of cliques covering every edge.

Hajebi's conjecture. For every integer t1t\ge 1, there exists ε>0\varepsilon>0 such that every Kt,tK_{t,t}-free graph GG has a clique cover of size

O(G2ε).O\left(|G|^{2-\varepsilon}\right).

The conjecture is attributed to Sepehr Hajebi, who proposed it at a conference in Lyon. The paper proves a related bound with ε=1/(2t)\varepsilon=1/(2t), 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.