← All problems

Girã o–Lewis–Popielarz conjecture on rainbow saturation of complete graphs

3 years old · documented by

Let KrK_r be the complete graph on rr vertices, let sat⁡(n,R(Kr))\operatorname{sat}(n,\mathcal{R}(K_r)) denote the minimum number of edges in an nn-vertex edge-colored graph containing no rainbow copy of KrK_r such that adding any non-edge in any color creates a rainbow copy of KrK_r, and fix r≥3r\geq 3. Girã o–Lewis–Popielarz conjecture. There exists a constant CrC_r depending only on rr such that, for every n≥2(r−2)n\geq 2(r-2),

sat⁡(n,R(Kr))=2(r−2)n+Cr.\operatorname{sat}(n,\mathcal{R}(K_r))=2(r-2)n+C_r.

The conjecture predicts an exact linear formula for rainbow saturation with infinitely many available colors.

References

Status

  • Refuted: Debsoumya Chakraborti, Kevin Hendrey, Ben Lund, Casey Tompkins. Rainbow saturation for complete graphs (arXiv, 2022) https://arxiv.org/abs/2212.04640

Source: Debsoumya Chakraborti, Kevin Hendrey, Ben Lund and Casey Tompkins, “Rainbow saturation for complete graphs”, arXiv:2212.04640 (2024).

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.