Fox, Grinshpun, and Pach's Gallai-Ramsey conjecture for complete graphs

About 2 years old · traced to

Let GRk(Kp)GR_k(K_p) be the smallest positive integer NN such that every Gallai coloring of KNK_N with at most kk colors contains a monochromatic copy of KpK_p. Let R(Kp)R(K_p) denote the two-color Ramsey number of KpK_p.

Fox, Grinshpun, and Pach's conjecture. For positive integers kk and pp,

GRk(Kp)={(R(Kp)−1)k/2+1,if k is even;(p−1)(R(Kp)−1)(k−1)/2+1,if k is odd.GR_k(K_p)= \begin{cases} (R(K_p)-1)^{k/2}+1, & \text{if } k \text{ is even};\\ (p-1)(R(K_p)-1)^{(k-1)/2}+1, & \text{if } k \text{ is odd}. \end{cases}

The formula is known for p=3p=3 and p=4p=4, whereas the precise value remains unresolved for p=5p=5. The source notes tension with the conjecture of McKay and Radziszowski, so the general conjecture remains open.

References

Primary source

Yanbo Zhang and Yaojun Chen, “Disproofs of four Gallai-Ramsey-type conjectures”, arXiv:2410.01549 (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.