Ramsey Chains in Linear Forests - Gary Chartrand; Ritabrato Chatterjee; Ping Zhang (Axioms, 2023)
Every red–blue coloring of the edges of a graph G results in a sequence <semantics>G1</semantics>, <semantics>G2</semantics>, …, <semantics>Gℓ</semantics> of pairwise edge-disjoint monochromatic subgraphs <semantics>Gi</semantics> (<semantics>1≤i≤ℓ</semantics>) of size i, such that <semantics>Gi</semantics> is isomorphic to a subgraph of <semantics>Gi+1</semantics> for <semantics>1≤i≤ℓ−1</semantics>. Such a sequence is called a Ramsey chain in G, and <semantics>ARc(G)</semantics> is the maximum length of a Ramsey chain in G, with respect to a red–blue coloring c. The Ramsey index <semantics>AR(G)</semantics> of G is the minimum value of <semantics>ARc(G)</semantics> among all the red–blue colorings c of G. If G has size m, then <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+12</mstyle></mfenced>≤m<<mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+22</mstyle></mfenced></semantics> 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, <semantics>AR(G)=k</semantics> if and only if <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+12</mstyle></mfenced>≤m<<mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+22</mstyle></mfenced></semantics>. Two of these classes are the matchings <semantics>mK2</semantics> and paths <semantics>Pm+1</semantics> 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 <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+12</mstyle></mfenced><m<<mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+22</mstyle></mfenced></semantics>, then <semantics>AR(F)=k</semantics>. Furthermore, if F is a linear forest of size <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+12</mstyle></mfenced></semantics>, where <semantics>k≥4</semantics>, that has at most <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k−12</mstyle></mfenced></semantics> components, then <semantics>AR(F)=k</semantics>, while for each integer t with <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k−12</mstyle></mfenced><t<<mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+12</mstyle></mfenced></semantics> there is a linear forest F of size <semantics><mfenced open="(" close=")"><mstyle scriptlevel="0" displaystyle="false">k+12</mstyle></mfenced></semantics> with t components, such that <semantics>AR(F)=k−1</semantics>.