Equality of the asymptotic clique bounds for bounded maximum average degree

About 3 years old · traced to

For each positive integer kk, let αk\alpha_k be the minimum value such that there is a constant ckc_k with

ω(G2)⩽αkD+ck\omega(G^2)\leqslant \alpha_kD+c_k

whenever GG is kk-degenerate and has maximum degree at most DD. Let βk\beta_k be the minimum value such that there is a constant dkd_k with

ω(G2)⩽βkD+dk\omega(G^2)\leqslant \beta_kD+d_k

whenever GG has maximum average degree less than 2k2k and maximum degree at most DD. The equality conjecture states that, for all k⩾2k\geqslant 2,

βk=αk.\beta_k=\alpha_k.

The paper proves the equality for k=2k=2, while its validity for larger values of kk remains open; the authors do not conjecture the precise values of either parameter.

References

Primary source

Daniel W. Cranston and Gexin Yu, “Cliques in Squares of Graphs with Maximum Average Degree less than 4”, arXiv:2305.11763 (2024).

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.