Sigma clique covering growth conjecture for complete multipartite graphs

For positive integers tt and dd, let Kt(d)K_t(d) denote the complete tt-partite graph with each part of size dd. Let ff be a function and let cc be a constant.

Sigma clique covering growth conjecture. For every positive integers tt and dd, if tf(d)t\geq f(d), then

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

The conjecture would make the known upper bound for scc(Kt(d))\operatorname{scc}(K_t(d)) sharp up to a constant factor for sufficiently large tt. It is proved in the source for d=2d=2, while the general case remains open.

Sources & referencesView supporting material

Primary source

Akbar Davoodi, Ramin Javadi and Behnaz Omoomi, “Sigma clique covering of graphs”, arXiv:1503.02380 (2015).

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.