Rainbow clique saturation conjecture

Let KrK_r be the complete graph on rr vertices, and let satt(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},

satt(n,R(Kr))=Θ(nlogn).\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.

Sources & referencesView supporting material

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.