Ramsey Chains in Linear Forests

Abstract

Every red–blue coloring of the edges of a graph G results in a sequence G1, G2, …, Gℓ of pairwise edge-disjoint monochromatic subgraphs Gi (1≤i≤ℓ) of size i, such that Gi is isomorphic to a subgraph of Gi+1 for 1≤i≤ℓ−1. Such a sequence is called a Ramsey chain in G, and ARc(G) is the maximum length of a Ramsey chain in G, with respect to a red–blue coloring c. The Ramsey index AR(G) of G is the minimum value of ARc(G) among all the red–blue colorings c of G. If G has size m, then k+12≤mk+22 for some positive integer k. It has been shown that there are infinite classes S of graphs, such that for every graph G of size m in S, AR(G)=k if and only if k+12≤mk+22. Two of these classes are the matchings mK2 and paths Pm+1 of size m. These are both subclasses of linear forests (a forest of which each of the components is a path). It is shown that if F is any linear forest of size m with k+12mk+22, then AR(F)=k. Furthermore, if F is a linear forest of size k+12, where k≥4, that has at most k−12 components, then AR(F)=k, while for each integer t with k−12tk+12 there is a linear forest F of size k+12 with t components, such that AR(F)=k−1.

Keywords

• red–blue edge coloring
• Ramsey chain
• Ramsey index
• linear forest