The Gallai-Ramsey conjecture for even cycles and paths

About 8 years old · traced to

Let n≥3n\ge3 and k≥2k\ge2. For each i∈{0,1,…,n−2}i\in\{0,1,\ldots,n-2\}, let Gi=P2i+3G_i=P_{2i+3}, and let Gn−1G_{n-1} be either C2nC_{2n} or P2n+1P_{2n+1}. Choose integers i1,…,iki_1,\ldots,i_k satisfying

n−1≥i1≥⋯≥ik≥0.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.

References

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.