Davoodi–Javadi–Omoomi lower-bound conjecture for sigma clique coverings
Let be the complete -partite graph with each part of size . Davoodi–Javadi–Omoomi's conjecture. There exists a function and a constant such that, for every positive integers and , if , then
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
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.