Rainbow clique saturation conjecture

About 9 years old · traced to

Let KrK_r be the complete graph on rr vertices, and let sat⁡t(n,R(Kr))\operatorname{sat}_{t}\left(n,\mathfrak{R}(K_r)\right) denote the minimum number of edges in an nn-vertex graph whose edges are coloured from a palette of tt colours and which is rainbow-saturated with respect to KrK_r. Rainbow clique saturation conjecture. For any integers rr and tt with t≥(r2)t\geq {r \choose 2},

sat⁡t(n,R(Kr))=Θ(nlog⁡n).\operatorname{sat}_{t}\left(n,\mathfrak{R}(K_r)\right)=\Theta(n\log n).

This conjecture predicts that the lower bound matches the known logarithmic upper bound for rainbow saturation of complete graphs, resolving the remaining gap in the asymptotic order.

References

Primary source

António Girão, David Lewis and Kamil Popielarz, “Rainbow saturation of graphs”, arXiv:1710.08025 (2019).

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.