Davoodi–Javadi–Omoomi lower-bound conjecture for sigma clique coverings
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.