We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Ramsey Chains in Linear Forests.
- Authors
Chartrand, Gary; Chatterjee, Ritabrato; Zhang, Ping
- Abstract
Every red–blue coloring of the edges of a graph G results in a sequence G 1 , G 2 , ..., G ℓ of pairwise edge-disjoint monochromatic subgraphs G i ( 1 ≤ i ≤ ℓ ) of size i, such that G i is isomorphic to a subgraph of G i + 1 for 1 ≤ i ≤ ℓ − 1 . Such a sequence is called a Ramsey chain in G, and A R c (G) is the maximum length of a Ramsey chain in G, with respect to a red–blue coloring c. The Ramsey index A R (G) of G is the minimum value of A R c (G) among all the red–blue colorings c of G. If G has size m, then k + 1 2 ≤ m < k + 2 2 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, A R (G) = k if and only if k + 1 2 ≤ m < k + 2 2 . Two of these classes are the matchings m K 2 and paths P m + 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 + 1 2 < m < k + 2 2 , then A R (F) = k . Furthermore, if F is a linear forest of size k + 1 2 , where k ≥ 4 , that has at most k − 1 2 components, then A R (F) = k , while for each integer t with k − 1 2 < t < k + 1 2 there is a linear forest F of size k + 1 2 with t components, such that A R (F) = k − 1 .
- Subjects
RAMSEY numbers; GRAPH coloring; SUBGRAPHS; INTEGERS
- Publication
Axioms (2075-1680), 2023, Vol 12, Issue 11, p1019
- ISSN
2075-1680
- Publication type
Article
- DOI
10.3390/axioms12111019