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

From papers

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;(p1)(R(Kp)1)(k1)/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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yanbo Zhang and Yaojun Chen, “Disproofs of four Gallai-Ramsey-type conjectures”, arXiv:2410.01549 (2024).

Solutions 0

No solutions have been posted yet.