Davoodi–Javadi–Omoomi lower-bound conjecture for sigma clique coverings

About 8 years old · traced to

Let Kt(d)K_t(d) be the complete tt-partite graph with each part of size dd. Davoodi–Javadi–Omoomi's conjecture. There exists a function ff and a constant c>0c>0 such that, for every positive integers tt and dd, if t≥f(d)t\geq f(d), then

scc⁡(Kt(d))≥cd2tlog⁡t.\operatorname{scc}(K_t(d))\geq cd^2t\log t.

This conjecture predicts that complete multipartite graphs attain, up to a constant factor, the logarithmic upper bound for the sigma clique cover number when the number of parts is sufficiently large relative to their size. The paper presents an equivalent set-system formulation and proves related lower bounds, but the stated asymptotic bound remains open.

References

Primary source

Akbar Davoodi, Dániel Gerbner, Abhishek Methuku and Máté Vizer, “On Clique Coverings of Complete Multipartite Graphs”, arXiv:1809.01443 (2018).

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.