The Gallai-Ramsey conjecture for even cycles and paths

Let n3n\ge3 and k2k\ge2. For each i{0,1,,n2}i\in\{0,1,\ldots,n-2\}, let Gi=P2i+3G_i=P_{2i+3}, and let Gn1G_{n-1} be either C2nC_{2n} or P2n+1P_{2n+1}. Choose integers i1,,iki_1,\ldots,i_k satisfying

n1i1ik0.n-1\ge i_1\ge\cdots\ge i_k\ge0.

Here GR(Gi1,,Gik)GR(G_{i_1},\ldots,G_{i_k}) is the least order of a complete graph such that every Gallai edge-coloring using at most kk colors contains a monochromatic copy of GijG_{i_j} in color jj for some jj. The Gallai-Ramsey conjecture for even cycles and paths. For all such nn, kk, and indices,

GR(Gi1,,Gik)=Gi1+j=2kij.GR(G_{i_1},\ldots,G_{i_k})=|G_{i_1}|+\sum_{j=2}^k i_j.

The displayed quantity is known to be a lower bound by an explicit Gallai-coloring construction; the conjecture asserts that this lower bound is always sharp. The source gives no resolution of the general upper bound.

Sources & referencesView supporting material

Primary source

Zi-Xia Song and Jingmei Zhang, “A conjecture on Gallai-Ramsey numbers of even cycles and paths”, arXiv:1803.07963 (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.