The Ramsey indexes of paths and cycles

Abstract

Let G be a graph of size m and let c be a red-blue colouring of the edges of G. A Ramsey chain in G with respect to c is a sequence $G_1,G_2,\dots ,G_{\ell }$ of pairwise edge-disjoint subgraphs of G such that each subgraph $G_i$ ($1\le i\le \ell$) is monochromatic of size i and $G_i$ is isomorphic to a subgraph of $G_{i+1}$ ($1\le i\le \ell -1$). The Ramsey index $A{R}_c(G)$ of G with respect to c is the maximum length of a Ramsey chain in G with respect to c. The Ramsey index $\mathrm{AR}(G)$ of G is the minimum value of $A{R}_c(G)$ among all red-blue colourings c of G. Consequently, if G is a graph of size m where $(\genfrac{}{}{0ex}{}{k+1}{2})\le m<(\genfrac{}{}{0ex}{}{k+2}{2})$, then $\mathrm{AR}(G)\le k$. It was proved that if $G=m{K}_2$ is a matching of size m or $G=K_{1,m}$ is a star of size m, then $\mathrm{AR}(G)=k$ if and only if $(\genfrac{}{}{0ex}{}{k+1}{2})\le m<(\genfrac{}{}{0ex}{}{k+2}{2})$. A question was posed as to whether there are other classes S of graphs with the property that for every sufficiently large integer m, every graph G of size m in S has the property that $\mathrm{AR}(G)=k$ if and only if $(\genfrac{}{}{0ex}{}{k+1}{2})\le m<(\genfrac{}{}{0ex}{}{k+2}{2})$. We show that all paths have this property and, as a consequence, all cycles have this property as well.

Keywords:

• Graph decomposition
• red-blue edge colouring
• Ramsey chain
• Ramsey index
• paths

2020 Mathematics Subject Classifications:

• 05C15
• 05C35
• 05C38
• 05C55
• 05C70

Acknowledgments

We thank the anonymous referees whose valuable suggestions resulted in an improved paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).