The Gallai-Ramsey reduction conjecture for rainbow P5P_{5}

Let P5P_{5} be the path on five vertices, let HH be a graph with no isolated vertices, and let kk be a positive integer. The Gallai-Ramsey number grk(P5:H)gr_k(P_{5}:H) is the minimum integer nn such that every coloring of KnK_n using at most kk colors contains either a rainbow copy of P5P_{5} or a monochromatic copy of HH. Let R3(H)R_3(H) denote the minimum integer nn such that every coloring of KnK_n using at most three colors contains a monochromatic copy of HH.

Gallai-Ramsey reduction conjecture. For any graph HH with no isolated vertices, we have

grk(P5:H)=R3(H).gr_k(P_{5}:H)=R_3(H).

The conjecture asserts that the Gallai-Ramsey problem for avoiding a rainbow P5P_{5} reduces to the three-color Ramsey number. The paper provides several results in support of this claim, but no resolution is supplied here.

Sources & referencesView supporting material

Primary source

Xihe Li, Pierre Besse, Colton Magnant, Ligong Wang and Noah Watts, “Gallai-Ramsey numbers for rainbow paths”, arXiv:1902.00612 (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.