Every red-blue coloring of the edges of a graph \(G\) results in a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{\ell}\) of pairwise edge-disjoint monochromatic subgraphs \(G_i\) (\(1 \le i \le \ell\)) of size \(i\) such that \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for \(1 \le i \le \ell-1\). Such a sequence is called a Ramsey chain in \(G\) and \(AR_c(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 \(AR_c(G)\) among all red-blue colorings \(c\) of \(G\). Several results giving the Ramsey indexes of graphs are surveyed. A galaxy is a graph each of whose components is a star. Results and conjectures on Ramsey indexes of galaxies are presented.
In 1987 a conjecture was stated that has drawn the interest of many researchers. When the famous mathematician Paul Erdős first learned of it, he immediately doubted its truth. Soon afterward, Erdős offered a cash reward (which was often common for Erdős) for a counterexample or a proof if it were true. This conjecture appeared in a book [9, p.72] containing a collection of graph theory problems that are associated with Erdős. Now, more than 35 years later, the conjecture has neither been proved nor disproved. Let us describe this conjecture.
If \(G\) is a graph of size \(m\) (without isolated vertices), then there is a unique positive integer \(k\) such that \({k+1\choose 2} \le m < {k+2\choose 2}\). The graph \(G\) is said to have an ascending subgraph decomposition {\(G_1\), \(G_2\), \(\ldots\), \(G_k\)} into \(k\) (pairwise edge-disjoint) subgraphs of \(G\) if \(G_i\) is isomorphic to a proper subgraph of \(G_{i+1}\) for \(i= 1, 2, \ldots, k-1\). The following conjecture was stated in [1].
Conjecture 1.1(The ascending subgraph decomposition conjecture). Every graph has an ascending subgraph decomposition.
If this conjecture was shown to be false, then the question arose of determining the maximum length \(\ell\) of a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{\ell}\) of \(\ell\) pairwise edge-disjoint subgraphs of \(G\) such that
(1) \(G_i\) has size \(i\) for each \(i \in [\ell]=\{1, 2, \ldots, \ell\}\) and
(2) \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for each \(i \in [\ell-1]\).
A sequence with properties (1) and (2) is called an ascending subgraph sequence of the graph \(G\) and the maximum length of such a sequence is the ascending subgraph index of \(G\), denoted by \(AS(G)\). The following conjecture is therefore equivalent to the Ascending Subgraph Decomposition Conjecture.
Conjecture 1.2(The ascending subgraph index conjecture).Let \(G\) be a nonempty graph of size \(m\). Then \(AS(G)=k\) if and only if \({k+1\choose 2} \le m < {k+2\choose 2}\).
This conjecture has drawn the attention of many researchers (see [2, 7, 8, 14, 19], for example). Among the several classes of graphs for which the conjecture has been verified are regular graphs (see [8, 15]). Two classes of graphs for which the conjecture can easily be verified are matchings \(mK_2\) (consisting of \(m\) components \(K_2\)) and stars \(K_{1, m}\). That is, for every positive integer \(m\), where \({k+1\choose 2} \le m < {k+2 \choose 2}\), there is an ascending subgraph decomposition {\(G_1\), \(G_2\), \(\ldots\), \(G_{k}\)} of the graph \(G\) if either \(G= mK_2\) or \(G = K_{1, m}\) such that \(G_i\) is isomorphic to a proper subgraph of \(G_{i+1}\) for \(1 \le i \le k-1\). If \(G = mK_2\), the subgraphs \(G_i\) are matchings and if \(G=K_{1, m}\), each subgraph \(G_i\) is a star.
This concept has a connection with edge colorings of graphs, which we now describe. By a red-blue edge coloring (or simply a red-blue coloring) of a graph \(G\), every edge of \(G\) is colored red or blue. In [2], the concept of ascending subgraph decomposition was extended to graphs possessing a red-blue coloring. Suppose that a red-blue coloring of a graph \(G= mK_2\) or \(G = K_{1, m}\) is given where \({k+1\choose 2} \le m < {k+2 \choose 2}\). It was shown in [5] that there is not only an ascending subgraph decomposition {\(G_1\), \(G_2\), \(\ldots\), \(G_{k}\)} of \(G\) but one in which each subgraph is monochromatic as well. This (perhaps unexpected) observation led to another concept, which is related to some topics in Ramsey Theory named for the British mathematician Frank Ramsey [21]. Ramsey theory is one of the most studied areas in combinatorics and graph theory with many highly nontrivial and beautiful results (see [10, 11, 12, 13, 16, 17, 20], for example). We refer to the books [2, 18] for basic definitions and notation in graph theory that are not defined here.
Let \(G\) be a graph (without isolated vertices) of size \(m\) with a red-blue coloring \(c\). An (ascending) Ramsey chain of \(G\) with respect to \(c\) is a sequence \(G_1\), \(G_2\), \(\ldots\), \(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}\) for \(1 \le i \le \ell-1\). The maximum length of a Ramsey chain of \(G\) with respect to \(c\) is the (ascending) Ramsey index \(AR_c(G)\) of \(G\). The (ascending) Ramsey index \(AR(G)\) of \(G\) is defined by \[AR(G)= \min\{AR_c(G): \mbox{ $c$ is a red-blue coloring of~$G$}\}.\]
Consequently, if \(AR(G)=\ell\) for some graph \(G\), then for every red-blue coloring of \(G\), there is a Ramsey chain of length \(\ell\) in \(G\), while there exists at least one red-blue coloring for which there is no Ramsey chain of length greater than \(\ell\). These concepts were introduced and studied in [2, 5], using somewhat different technology, and studied further in [3, 6].
Two immediate observations dealing with Ramsey indexes of graphs are the following.
Observation 2.1. If \(H\) and \(G\) are graphs such that \(H \subseteq G\), then \(AR(H) \le AR(G)\). Consequently, if \(AR(H) \ge k\) for each graph \(H\) of size \(m\), then \(AR(G) \ge k\) for every graph \(G\) of size \(m+1\).
Observation 2.2. If \(G\) is a graph of size \(m\) where \(m < {k+2 \choose 2}\) for a positive integer \(k\), then \(AR(G) \le k\).
Results that have been obtained on matchings, stars, cycles, and paths are stated as follows.
Theorem 2.3. [3, 5, 6] If \(G\in \{mK_2, K_{1, m}, C_m, P_{m+1}\}\) where \(m \ge 3\), then \[AR(G) = k \text{ if and only if }{k+1 \choose 2} \le m < {k+2 \choose 2}.\]
The following is a consequence of Theorem 2.3.
Corollary 2.4. If \(G\in \{mK_2, K_{1, m}, C_m, P_{m+1}\}\) where \(m \ge 3\), then \(AR(G) = \left\lfloor\frac{-1 + \sqrt{1+8m}}{2}\right\rfloor.\)
With the aid of Ramey indexes of matchings and stars, the Ramsey index of a graph consisting of a matching of any size and a star of any size, namely the graph \(aK_2+K_{1, b}\) where \(a\ge 1\) and \(b \ge 2\) has also been determined.
Theorem 2.5. [5] For integers \(a\ge 1\) and \(b\ge 2\), \[AR(aK_2+K_{1, b})=\left\{ \begin{array}{cl} AR((a+1)K_2) & \mbox{ if $b \le a$}\\[.2cm] AR(K_{1, b}) & \mbox{ if $b \ge a+2$}\\[.2cm] AR(K_{1, b+1}) & \mbox{ if $b = a+1$.} \end{array}\right.\]
The complete graph \(K_n\) of order \(n\) has size \({n \choose 2}\) and so \(AR(K_n) \le n-1\). The following conjecture was made.
Conjecture 2.6. [5] For every integer \(n \ge 3\), \(AR(K_n) = n-1\).
Conjecture 2.6 has been verified for \(3 \le n \le 6\).
Every graph \(G\) of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) mentioned in Theorem 2.3 has \(AR(G)=k\). This brings up the question of finding graphs \(G\) of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for which \(AR(G) \ne k\). Thus, \(AR(G) \le k-1\). This led to an investigation of double stars (trees of diameter 3). For integers \(a\) and \(b\) with \(2 \le a \le b\), the double star \(S_{a, b}\) has a vertex of degree \(a\), a vertex of degree \(b\), and all other vertices have degree 1. The double star \(S_{a, b}\) has order \(a+b\) and size \(a+b-1\). Thus, if \({k+1\choose 2} \le a+b-1 < {k+2\choose 2}\), then \(AR(S_{a, b}) \le k\). In the case when \(a = 2\), the double star \(S_{2, b}\) has size \(m=b+1\). Therefore, if \({k+1\choose 2} \le b+1 < {k+2\choose 2}\), then \(AR(S_{2, b})\le k\). In fact, the following was obtained.
Theorem 2.7. [5] Let \(b \ge 2\) be an integer. Then \[AR(S_{2, b})=k\text{ if and only if }{k+1\choose 2}+1 \le b +1 < {k+2\choose 2}+1.\]
For the double star \(S_{3, b}\) where \(b \ge 3\), which has size \(m=b+2\), we have the following.
Theorem 2.8. [5] Let \(b \ge 3\) be an integer.
1. If \(b+2= {k+1\choose 2}\) or \(b+2= {k+2\choose 2}+1\), then \(AR(S_{3, b}) = k-1\).
2. If \({k+1\choose 2} +2 \le b+2 < {k+2\choose 2}\), then \(AR(S_{3, b}) = k\).
More generally, we have the following.
Theorem 2.9. [5] Let \(2 \le a \le b\) be integers. If \(a+b-1 \in \left\{{k+1\choose 2}, {k+1\choose 2}+1,\ldots, {k+1\choose 2}+a\right.\\\left.-2\right\}\), then \(AR(S_{a, b}) = k-1\).
Matchings and paths are all subclasses of linear forests. A linear forest is a forest every component of which is a path. Here, we are only concerned with linear forests without isolated vertices. Paths and matchings are linear forests with the minimum and maximum number of components. In [4], it was shown that Theorem 2.3 can be extended to include linear forests distinct from paths and matchings.
Theorem 2.10. [4] If \(H\) is a linear forest of size \(m\) where \({k+1\choose 2} < m < {k+2 \choose 2}\) for some integer \(k\ge 3\), then \(AR(H)=k\).
A linear forest is \(k\)-binomial (or simply binomial) if its size is \({k+1\choose 2}\) for some positive integer \(k\).
Theorem 2.11. [4] If \(H\) is a \(k\)-binomial linear forest where \(k \ge 4\) with at most \({k-1\choose 2}\) components, then \(AR(H)=k\).
By Theorems 2.3 and 2.11, every \(k\)-binomial linear forest where \(k \ge 4\) with \(t\) components such that either \(t = {k+1\choose 2}\) or \(1 \le t \le {k-1\choose 2}\) has Ramsey index \(k\). A natural question concerns whether these bounds on \(t\) can be improved. As we will see, no such improvement is possible. First, we provide a necessary and sufficient condition for a \(k\)-binomial linear forest to have Ramsey index \(k-1\).
Theorem 2.12. [4] Let \(H= Q_{q_1}+Q_{q_2} +\cdots + Q_{q_t}\) be a \(k\)-binomial linear forest of size \(\sum\limits_{i=1}^t q_i={k+1\choose 2}\) for some integer \(k \ge 4\) with \(t\) components where \({k-1\choose 2} < t < {k+1\choose 2}\) where \(s= \sum\limits_{i=1}^t \left\lfloor\frac{q_i}{2}\right\rfloor\) is the maximum number of pairwise edge-disjoint copies of \(Q_2\) in \(H\).
(1) If \(s > k\), then \(AR(H)=k\).
(2) If \(s = k\) and \(H\) contains two components of even size \(4\) or more, then \(AR(H)=k-1\); otherwise, \(AR(H) = k\).
(3) If \(s = k-1\) and \(H\) contains at least one component of even size \(4\) or more, then \(AR(H)=k-1\); otherwise, \(AR(H) = k\).
(4) If \(s \le k-2\), then \(AR(H)=k-1\).
We have seen (by Theorems 2.3 and 2.11) that if \(H\) is a \(k\)-binomial linear forest where \(k \ge 4\) with \(t\) components whether \(t = {k+1\choose 2}\) or \(1 \le t \le {k-1\choose 2}\), then \(AR(H)=k\). With the aid of Theorem 2.12, it was shown that these bounds on \(t\) cannot be improved.
Theorem 2.13. [4] For every two integers \(t\) and \(k\) where \({k-1\choose 2} < t < {k+1\choose 2}\) and \(k \ge 4\), there is a \(k\)-binomial linear forest \(H\) with \(t\) components such that \(AR(H)=k-1\).
According to Theorem 2.11, if \(H\) is a linear forest of size \({k+1\choose 2}\) for some integer \(k \ge 4\) with relatively few components, then \(AR(H)=k\). Consequently, if \(H\) is a forest of size \({k+1\choose 2}\) for some integer \(k \ge 4\) where every component of \(H\) is a path and \(H\) has a limited number of components, then \(AR(H)=k\). We have seen that if \(H\) is star of size \({k+1\choose 2}\), then \(AR(H)=k\) as well. This brings up the question if \(H\) is a forest of size \({k+1\choose 2}\) having a limited number of components where every component is a star, then whether \(AR(H)=k\) in this case as well. We investigate this problem now.
We denote the star \(K_{1, m}\) of size \(m\) by \(S_m\). A galaxy is a graph each of whose components is a star. For a positive integer \(s\), an \(s\)-galaxy consists of \(s\) stars. Thus, for an \(s\)-galaxy of size \(m\), it follows that \(1 \le s \le m\). A \(1\)-galaxy of size \(m\) is the star \(S_m\) and an \(m\)-galaxy of size \(m\) is the matching \(mK_2= mS_1\). The following observation is useful.
Observation 3.1. If \(H\) is a galaxy of size \(m \ge 3\), then \(AR(H) \le AR(S_{m})\).
Proof. Suppose that \(AR(H)= k\). Then every 2-edge coloring of \(H\) produces a Ramsey chain of length \(k\) in \(H\) and so \(m \ge {k+1\choose 2}\). Observe that if \(F\) and \(G\) are graphs without isolated vertices such that \(F \subseteq G\), then \(AR(F) \le AR(G)\). It then follows Theorem 2.3 that \(AR(S_m) \ge AR\left(S_{{k+1\choose 2}}\right) = k = AR(H)\). ◻
Strict inequality in Observation 3.1 can occur. For example, consider the \(3\)-galaxies \(2S_1+S_4\) of size 6 and \(2S_1+S_5\) of size \(7\). Figure 1 shows a red-blue coloring for each of these two graphs, where a bold edge indicates a red edge and a thin edge indicates a blue edge. Since there is no Ramsey chain of length 3 with respect to each of these colorings, it follows that \(AR(2S_1+S_4)= AR(2S_1+S_5)=2\). On the other hand, \(AR(S_6)=AR(S_7)=3\) by Theorem 2.3. Thus, \(AR(2S_1+S_4) < AR(S_6)\) and \(AR(2S_1+S_5) < AR(S_7)\).
Proposition 3.2. Let \(H=S_x+S_y\) be a \(2\)-galaxy such that \({k+1\choose 2} \le x+y < {k+2\choose 2}\) where \(k \ge 3\).
(a) If \(x+y={k+1\choose 2}\) and \(\min\{x, y\} \le k-2\), then \(AR(H)=k-1\).
(b) If \(\max\{x, y\} \ge {k+1\choose 2}\), then \(AR(H)=k\).
Proof. Assume, without loss of generality, that \(x=\min\{x, y\}\) and \(\max\{x, y\} = y\). To verify (a), suppose that \(x+y={k+1\choose 2}\) and \(x \le k-2\). Then \(y = {k+1\choose 2}-x\ge {k+1\choose 2}-(k-2) = {k\choose 2}+2\) and so \(S_{{k\choose 2}} \subseteq S_y \subseteq H\). It then follows by Observation 3.1 that \(AR(H) \ge k-1\). Next, we show that \(AR(H) \le k-1\). Let \(c\) be a \(2\)-edge coloring of \(H\) resulting in monochromatic subgraphs \(H_1=2S_1\) and \(H_2=S_{x-1}+S_{y-1}\). We claim that there is no Ramsey chain of length \(k\) in \(H\). Suppose that there is a Ramsey chain \(G_1, G_2, \ldots, G_k\) of length \(k\) in \(H\). Since the size of \(H\) is \({k+1\choose 2}\), it follows that \(\{G_1, G_2, \ldots, G_k\}\) is a decomposition of \(H\). Necessarily, \(G_2= H_1=2S_1\). This implies that \(2S_1 \subseteq G_i\subseteq H_2\) for \(3 \le i \le k\) and that \(G_i\) contains an edge of \(H_2\) belonging to \(S_x\). Since \(S_x\) contains at most \(k-3\) edges of \(H_2\), this is impossible. Thus, \(AR(H)= k-1\).
To verify (b), suppose that \(y\ge {k+1\choose 2}\). Then \(S_{{k+1\choose 2}} \subseteq H\) and so \(AR(H) \ge k\) by by Observation 3.1. Furthermore, \(AR(H) \le k\) by Observation 2.2. Therefore, \(AR(H)=k\). ◻
If \(S_1= K_2\) is a component of a \(2\)-galaxy of a sufficiently large size, then the following is consequence of Proposition 3.2.
Proposition 3.3. If \(H= S_1+S_{m-1}\) is a \(2\)-galaxy of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k\ge 3\), then \[AR(H)= \left\{\begin{array}{cl} k-1 & \mbox{ if $m={k+1 \choose 2}$}\\[.1cm] k & \mbox{otherwise}. \end{array} \right.\]
Let \(H\) be a \(2\)-galaxy of size \(m\) where \({3+1\choose 2} = 6 \le m < 10= {3+2\choose 2}\) for \(k=3\). If \(m=6\), then \(AR(S_1+S_5)=2\) and \(AR(S_2+S_4)=AR(2S_3)=3\). If \(7 \le m \le 9\), then \(H\) contains a subgraph isomorphic to one of \(S_6\), \(S_2+S_4\), or \(2S_3\). Thus, \(AR(H)\ge 3\) and so \(AR(H)=3\). Hence, we may assume that \(k \ge 4\). Next, we determine \(AR(S_2+S_{m-2})\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k\ge 4\). First, we present some preliminary results.
Lemma 3.4. If \(k \ge 7\) is an integer, then \(k \le \left\lceil\frac{{k+1 \choose 2}/2}{2}\right\rceil\) and strict inequality holds for \(k \ge 8\).
Proof. If \(k = 7\), then \(k= \left\lceil\frac{{k+1 \choose 2}/2}{2}\right\rceil\). If \(k \ge 8\), then \(k(k-7) > 0\). Thus, \(8k <k^2+k\) and so \(4k < {k+1\choose 2}\). Hence, \(k < \frac{{k+1\choose 2}/2}{2} \le \left\lceil\frac{{k+1 \choose 2}/2}{2}\right\rceil\). ◻
Lemma 3.5. Let \(m = {k+1\choose 2}\) for some integer \(k \ge 5\). For every two positive integers \(m_1\) and \(m_2\) with \(m=m_1+m_2\) and \(m_1, m_2 \notin \{2, 4\}\), there exists a partition of \([k]=\{1, 2, \ldots, k\}\) into two subsets \(A=\{a_1, a_2, \ldots, a_{k_1}\}\) and \(B=\{b_1, b_2, \ldots, b_{k_2}\}\), where \(k_1+k_2=k\), \[1= a_1< a_2 < \cdots < a_{k_1}\le \left\lceil\frac{m_1}{2}\right\rceil,\text{ and }b_1< b_2 < \cdots < b_{k_2} = k\le \left\lceil\frac{m_2}{2}\right\rceil,\] such that \(\sum\limits_{i=1}^{k_1} a_i= m_1\) and \(\sum\limits_{i=1}^{k_2} b_i= m_2\).
Proof. We proceed by induction on \(k \ge 5\).
\(\star\) If \(k = 5\), then \(m={5+1\choose 2} = 15\).
Let \(m_1\) and \(m_2\) be two positive integers such that \(m_1+m_2= 15\) and \(m_1, m_2 \notin \{2, 4\}\). We may assume that \(m_1 \le m_2\). Thus, \(m_1 \le 7\) and \(m_1 \notin\{2, 4\}\). Partitions \(\{A, B\}\) of \([5]\) with the desired properties are listed below for all possible such pairs \((m_1, m_2)\):
For \(m_1=1\), let \(A=\{1\}\) and \(B =\{2, 3, 4, 5\}\).
For \(m_1 = 3\), let \(A=\{1, 2\}\) and \(B = \{3, 4, 5\}\).
For \(m_1 = 5\), let \(A=\{1, 4\}\) and \(B = \{2, 3, 5\}\).
For \(m_1 = 6\), let \(A=\{1, 2, 3\}\) and \(B = \{4, 5\}\).
For \(m_1 = 7\), let \(A=\{1, 2, 4\}\) and \(B =\{3, 5\}\).
\(\star\) If \(k = 6\), then \(m={6+1\choose 2} = 21\).
Let \(m_1\) and \(m_2\) be two positive integers such that \(m_1+m_2= 21\) and \(m_1, m_2 \notin \{2, 4\}\). We may assume that \(m_1 \le m_2\). Thus, \(m_1 \le 10\) and \(m_1 \notin\{2, 4\}\). Partitions \(\{A, B\}\) of \([6]\) with the desired properties are listed below for all possible such pairs \((m_1, m_2)\):
For \(m_1=1\), let \(A=\{1\}\) and \(B =\{2, 3, 4, 5, 6\}\).
For \(m_1 = 3\), let \(A=\{1, 2\}\) and \(B = \{3, 4, 5, 6\}\).
For \(m_1 = 5\), let \(A=\{1, 4\}\) and \(B = \{2, 3, 5, 6\}\).
For \(m_1 = 6\), let \(A=\{1, 2, 3\}\) and \(B = \{4, 5, 6\}\).
For \(m_1 = 7\), let \(A=\{1, 2, 4\}\) and \(B =\{3, 5, 6\}\).
For \(m_1 = 8\), let \(A=\{1, 3, 4\}\) and \(B =\{2, 5, 6\}\).
For \(m_1 = 9\), let \(A=\{1, 3, 5\}\) and \(B =\{2, 4, 6\}\).
For \(m_1 = 10\), let \(A=\{1, 4, 5\}\) and \(B =\{2, 3, 6\}\).
Hence, the statement is true for \(k =5, 6\). Assume that the statement is true for some integer \(k \ge 6\). We show that the statement is true for \(k+1\). For an integer \(m = {k+2\choose 2}\) where \(k \ge 6\), let \(m_1\) and \(m_2\) be two positive integers such that \(m=m_1+m_2\) and \(m_1, m_2 \notin \{2, 4\}\). We may assume that \(m_1 \le m_2\). Thus, \(m_2 \ge m/2\). Let \(m_1'= m_1\) and \(m_2'= m_2-(k+1)\). Thus, \(m_1'= m_1 \notin \{2, 4\}\) and \(m_1' + m_2'= {k+1\choose 2}\). Since \(k \ge 6\), it follows that \(k(k-1) \ge 30 > 22\) and so \((k^2+3k+2) – 4k – 4> 20\). Thus, \(\frac{{k+2\choose 2}}{2} -k-1 \ge 5\). Since \(m'_2 = m_2-(k+1) \ge\frac{m}{2} – (k+1) = \frac{{k+2\choose 2}}{2} -(k+1) \ge 5\), it follows that \(m'_2 \notin \{2, 4\}\). By the induction hypothesis, it follows that \([k]\) can be partitioned into two sets \(A=\{a_1, a_2, \ldots, a_{k_1}\}\) and \(B=\{b_1, b_2, \ldots, b_{k_2}\}\), where \(k_1+k_2=k\), \[1= a_1< a_2 < \cdots < a_{k_1} \le \left\lceil\frac{m'_1}{2}\right\rceil= \left\lceil\frac{m_1}{2}\right\rceil,\]and \[b_1< b_2 < \cdots < b_{k_2} = k \le \left\lceil\frac{m'_2}{2}\right\rceil= \left\lceil\frac{m_2-(k+1)}{2}\right\rceil,\] such that \(\sum\limits_{i=1}^{k_1} a_i = m'_1= m_1\) and \(\sum\limits_{i=1}^{k_2} b_i = m'_2= m_2-(k+1)\). Now, let \(X = A=\{a_1, a_2, \ldots, a_{k_1}\}\) and \(Y = B \cup \{k+1\}= \{b_1, b_2, \ldots, b_{k_2}, k+1\}\). Then \(\{X, Y\}\) forms a partition of \([k+1]\) with \(|X|+|Y|= k_1+(k_2+1) = k+1\). Since \(m_2 \ge \frac{m}{2} =\frac{{k+2 \choose 2}}{2}\) and \(k+1\ge 7\), it follows by Lemma 3.4 that \(k+1 \le \left\lceil\frac{{k+2 \choose 2}/2}{2}\right\rceil \le \left\lceil\frac{m_2}{2}\right\rceil\). Furthermore, \(\sum\limits_{x \in X} x =m_1'= m_1\) and \(\sum\limits_{y\in Y} y = m_2'+(k+1)= m_2\). Therefore, \(\{X, Y\}\) is a partition of \([k+1]\) with the desired property. ◻
We are now prepared to determine the Ramsey index of every \(2\)-galaxy of sufficiently large size where one component is \(S_2=P_3 = K_{1, 2}\).
Theorem 3.6. If \(H= S_2+S_{m-2}\) is a \(2\)-galaxy of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k\ge 4\), then \[AR(H)= \left\{\begin{array}{cl} k-1 & \mbox{ if $m={k+1 \choose 2}$}\\[.1cm] k & \mbox{otherwise}. \end{array} \right.\]
Proof. By Proposition 3.2, if \(m={k+1\choose 2}\), then \(AR(H)=k-1\) (since \(2 \le k-2\) when \(k \ge 4\)); while if \({k+1\choose 2} +2\le m < {k+2\choose 2}\), then \(AR(H)=k\). Thus, we may assume that \(m= {k+1\choose 2}+1\). By Observation 2.2, it suffices to show that \(AR(H) \ge k\). Let \(c\) be a \(2\)-edge coloring of \(H\) using the colors \(1\) and \(2\). For \(i = 1, 2\), let \(H_i\) be the subgraph of size \(m_i\) in \(H\) induced by the edges of \(H\) colored \(i\), where \(1\le m_1 \le m_2\) and \(m_1+m_2 = m= {k+1\choose 2} +1\). There are six cases, according to whether \(m_1\in \{1, 2, 3, 4, 5\}\) or \(m_1\ge 6\). In each case, we consider the possible structures of \(H_1\) and \(H_2\) and show that there is a Ramsey chain of length \(k\) in \(H\). These six cases are listed as follows. Since the arguments in the proofs of Cases 1–5 are similar, we will only prove Cases 5 and 6.
Case 1. \(m_1=1\). Thus, \(H_1=S_1\) and \(H_2\in \{S_1+S_{m-2}, S_2+S_{m-3}\}\).
Case 2. \(m_1=2\). Thus, \(H_1\in \{2S_1, S_2\}\), \(m_2 = {k+1\choose 2}-1\), and \[H_2\in \{S_1+S_{m-3}, S_{m-2}, S_2+S_{m-4}\}.\]
Case 3. \(m_1=3\). Thus, \(H_1\in \{S_3, S_1+S_2\}\), \(m_2 = {k+1\choose 2}-2\), and \[H_2\in \{S_2+S_{m-5}, S_1+S_{m-4}, S_{m-3}\}.\]
Case 4. \(m_1=4\). Thus, \(H_1\in \{S_1+S_3, 2S_2, S_4\}\), \(m_2 = {k+1\choose 2}-3\), and \[H_2\in \{S_1+S_{m-5}, S_{m-4}, S_2+S_{m-6}\}.\]
Case 5. \(m_1= 5\). Thus, \(H_1\in \{S_1+S_4, S_2+S_3, S_5\}\), \(m_2 = {k+1\choose 2}-4\), and \[H_2\in \{S_1+S_{m-6}, S_{m-5}, S_2+S_{m-7}\}.\]
\(\star\) First, suppose that \(H_1= S_1+S_4\). Then \(H_2=S_1+S_{m-6}\), where \(m-6={k+1\choose 2}-5\). Since \(2+3+5+6+ \cdots + k = {k+1\choose 2} – 5\), there is an ascending subgraph sequence \(S_2, S_3, S_5, S_6, \ldots, S_k\) in \(S_{m-6}\subseteq H_2\). Let \(G_1=S_1\subseteq H_1\) and \(G_4=S_4\subseteq H_1\). Thus, \(S_1, S_2, S_3, S_4, S_5, \ldots, S_k\) is a Ramsey chain of length \(k\) in \(H\).
\(\star\) Next, suppose that \(H_1=S_2+S_3\). Then \(H_2=S_{m-5}\) where \(m-5={k+1\choose 2} -4\). Since \(1+4+5+\cdots +k = {k+1\choose 2} -5\), the subgraph \(S_{m-5}\) in \(H_2\) can be decomposed into \(S_1, S_4, S_5, \ldots, S_k\). Let \(G_2=S_2\subseteq H_1\) and \(G_3=S_3\subseteq H_1\). Thus, \(S_1, S_2, S_3, S_4, \ldots, S_k\) is a Ramsey chain of length \(k\) in \(H\).
\(\star\) Finally, suppose that \(H_1=S_5\). Then \(H_2=S_2+S_{m-7}\), where \(m-7={k+1\choose 2} -6= 2+3+4+6+7+\cdots +k\). Then \(S_{m-7}\) can be decomposed into \(S_2, S_3, S_4, S_6, S_7, \ldots, S_k\) and we denote the component \(S_2\) in \(H_2\) by \(S_2'\). Let \(G_1=S_1\subseteq S_2'\subseteq H_2\) and \(G_5=H_1=S_5\). Thus, \(S_1, S_2, S_3, S_4, S_5, \ldots, S_k\) is a Ramsey chain of length \(k\) in \(H\).
Case 6. \(m_1\ge 6\). Thus, \(H_1\in \{S_1+S_{m_1-1}, S_2+S_{m_1-2}, S_{m_1}\}\), \(m_2 = {k+1\choose 2}-m_1+1\), and \[H_2\in \{S_1+S_{{k+1\choose 2}-m_1}, S_{{k+1\choose 2}-m_1+1}, S_2+S_{{k+1\choose 2}-m_1-1}\}.\]
\(\star\) First, suppose that \(H_1= S_1+S_{m_1-1}\). Then \(H_2=S_1+S_{{k+1\choose 2}-m_1}\). Since \(m_1 \ge 6\), it follows that \(m_2-1\ge 5\). Since \(m=m_1+m_2 = {k+1\choose 2}+1\), we have \(m_1+(m_2-1) = {k+1\choose 2}\). By Lemma 3.5, there exists a partition of \([k]=\{1, 2, \ldots, k\}\) into two subsets \(A=\{a_1, a_2, \ldots, a_{k_1}\}\) and \(B=\{b_1, b_2, \ldots, b_{k_2}\}\), where \(k_1+k_2=k\), \(a_1< a_2 < \cdots < a_{k_1}\le \left\lceil\frac{m_1}{2}\right\rceil\), and \(b_1< b_2 < \cdots < b_{k_2}\le \left\lceil\frac{m_2-1}{2}\right\rceil\) such that \(a_1=1\), \(b_{k_2}= k\), \(\sum\limits_{i=1}^{k_1} a_i= m_1\), and \(\sum\limits_{i=1}^{k_2} b_i= m_2-1\). Then \(H_1\) can be decomposed into \(S_1=S_{a_1}, S_{a_2}, \ldots, S_{a_{k_1}}\) and the subgraph \(S_{{k+1\choose 2}-m_1}\) can be decomposed into \(S_{b_1}, S_{b_2}, \ldots, S_{b_{k_2}}\). Thus, \(S_1, S_2, S_3, \ldots, S_k\) is a Ramsey chain of length \(k\) in \(H\).
\(\star\) Next, suppose that \(H_1=S_2+S_{m_1-2}\). Then \(H_2=S_{{k+1\choose 2}-m_1+1}\). Then \(m_1-1\ge 5\) and \((m_1-1)+ m_2 = {k+1\choose 2}\). By Lemma 3.5, there exists a partition of \([k]=\{1, 2, \ldots, k\}\) into two subsets \(A=\{a_1, a_2, \ldots, a_{k_1}\}\) and \(B=\{b_1, b_2, \ldots, b_{k_2}\}\), where \(k_1+k_2=k\), \(a_1< a_2 < \cdots < a_{k_1}\le \left\lceil\frac{m_1-1}{2}\right\rceil\), and \(b_1< b_2 < \cdots < b_{k_2}\le \left\lceil\frac{m_2}{2}\right\rceil\) such that \(a_1=1\), \(b_{k_2}= k\), \(\sum\limits_{i=1}^{k_1} a_i= m_1\), and \(\sum\limits_{i=1}^{k_2} b_i= m_2\). The subgraph \(S_1+S_{m_1-2}\) of \(H_1\) can be decomposed into \(S_1=S_{a_1}, S_{a_2}, \ldots, S_{a_{k_1}}\) and \(H_2\) can be decomposed into \(S_{b_1}, S_{b_2}, \ldots, S_{b_{k_2}}\). Thus, \(S_1, S_2, S_3, \ldots, S_k\) is a Ramsey chain of length \(k\) in \(H\).
\(\star\) Finally, suppose that \(H_1=S_{m_1}\). Then \(H_2=S_2+S_{{k+1\choose 2}-m_1-1}\). Since \(m_2 \ge m_1 \ge 6\) and \(m = m_1+m_2={k+1\choose 2} +1\), it follows that \({k+1\choose 2}-m_1 \ge 5\). By Lemma 3.5, there exists a partition of \([k]=\{1, 2, \ldots, k\}\) into two subsets \(A=\{a_1, a_2, \ldots, a_{k_1}\}\) and \(B=\{b_1, b_2, \ldots, b_{k_2}\}\), where \(k_1+k_2=k\), \(a_1< a_2 < \cdots < a_{k_1}\le \left\lceil\frac{m_1}{2}\right\rceil\), and \(b_1< b_2 < \cdots < b_{k_2}\le \left\lceil\frac{{k+1\choose 2}-m_1}{2}\right\rceil\) such that \(a_1=1\), \(b_{k_2}= k\), \(\sum\limits_{i=1}^{k_1} a_i= m_1\), and \(\sum\limits_{i=1}^{k_2} b_i= {k+1\choose 2}-m_1\). Then \(H_1= S_{m_1}\) can be decomposed into \(\{S_{a_1}, S_{a_2}, \ldots, S_{a_{k_1}}\}\) and \(S_{{k+1\choose 2}-m_1}\) can be decomposed into \(\{S_{b_1}, S_{b_2}, \ldots, S_{b_{k_2}}\}\) where \(S_{b_{k_2}}= S_k\). Since either \(S_{a_{k_1}}= S_{k-1}\) or \(S_{b_{k_2-1}}= S_{k-1}\), it follows that \(S_{{k+1\choose 2}-m_1-1}\) can be decomposed into \(\{S_{b_1}, S_{b_2}, \ldots, S_{b_{k_2-1}}, S_{b_{k_2}-1}\}\), where the last two stars in the decomposition may be the same (that is, it is possible that \(b_{k_2-1}=b_{k_2}-1\)). Thus, \(S_1+ S_{{k+1\choose 2}-m_1-1}\) can be decomposed into \(\{S_{b_1}, S_{b_2}, \ldots, S_{b_{k_2-1}}, S_1+S_{b_{k_2}-1}\}\). Therefore, \(S_1, S_2, S_3, \ldots, S_{k-1}, S_1+S_{k-1}\) is a Ramsey chain of length \(k\) in \(H\). ◻
We now investigate \(2\)-galaxies \(S_3+S_{m-3}\) of size \(m \ge 6\). We saw that \(AR(S_3+S_{m-3})= 3\) for \({3+1\choose 2} =6\le m < 10= {3+2\choose 2}\). Next, we show that \(AR(S_3+S_{m-3}) = 4\) for \({4+1\choose 2} =10 \le m < 15= {4+2\choose 2}\).
Proposition 3.7. For each integer \(m\) with \(10 \le m \le 14\), \(AR(S_3+S_{m-3}) = 4\).
Proof. Let \(m\) be an integer with \(10 \le m \le 14\). Since the size of \(S_3+S_{m-3}\) is less than \({5+1\choose 2}= 15\), it follows by Observation 2.2 that \(AR(S_3+S_{m-3}) \le 4\). Thus, it remains to show that \(AR(S_3+S_{m-3}) \ge 4\). By Observation 2.1, it suffices to show that \(AR(S_3+S_{7}) \ge 4\).
Let \(H = S_3+S_7\). We show that for every red-blue coloring of \(H\), there is a Ramsey chain in \(H\) of length 4. Let \(c\) be an arbitrary red-blue coloring of \(H\) with red subgraph \(H_1\) of size \(m_1\) and blue graph \(H_2\) of size \(m_2\). We may assume that \(1 \le m_1 \le m_2\) and so \(1 \le m_1 \le 5\). We consider five cases, according the value of \(m_1\). In each case, we show that there is a Ramsey chain \(G_1, G_2, G_3, G_4\) of length 4 in \(H\). Hence, \(|E(G_i)|= i\) for \(1 \le i \le 4\) and so \(\{G_1, G_2, G_3, G_4\}\) is a decomposition of \(H\).
Case 1. \((m_{1},m_{2})=(1,9)\). Then \((H_1, H_2)\in \{(S_1, S_{2}+S_{7}), (S_1, S_{3}+S_{6})\}\). Since \(S_{7}\) can be decomposed into \(S_{3}, S_{4}\), and \(S_{6}\) can be decomposed into \(S_{2}, S_{4}\), it follows that \(S_1, S_2, S_3, S_4\) is a Ramsey Chain of length \(4\) in \(H\).
Case 2. \((m_{1},m_{2})=(2,8)\). Thus, \((H_1, H_2)\in \{(S_{2}, S_{1}+S_{7}),(S_{2},S_{3}+S_{5}), (2S_{1},S_{2}+S_{6})\}\). Since \(\{G_1, G_2, G_3, G_4\}\) is a decomposition of \(H\), it follows that \(G_2= H_1\). First, suppose that \((H_{1},H_{2}) \in \{(S_{2}, S_{1}+S_{7}),(S_{2},S_{3}+S_{5})\}\). Since \(S_{7}\) can be decomposed into \(S_{3},S_{4}\) and \(S_{5}\) can be decomposed into \(S_{1},S_{4}\), it follows that \(S_{1}, S_2, S_3, S_{4}\) is a Ramsey Chain of length \(4\) in \(H\). Next, suppose that \((H_{1},H_{2})=(2S_{1},S_{2}+S_{6})\). Then \(S_2\) can be decomposed into \(S_1, S_1\) and \(S_{6}\) can be decomposed into \(S_{1}, S_{2}, S_{3}\). Let \(G_{1}=S_{1} \subseteq H_{2}\), \(G_2= 2S_1 = H_1\), \(G_{3}=S_{1}+S_{2}\subseteq H_2\), and \(G_{4}=S_{1}+S_{3} \subseteq H_{2}\). Then \(G_{1}, G_2, G_3, G_{4}\) is a Ramsey chain of length \(4\) in \(H\).
Case 3. \((m_{1},m_{2})=(3,7)\). Thus, \((H_{1},H_{2})\in \{(S_{3},S_{7}),(S_{3},S_{3}+S_{4}), (S_{1}+S_{2},S_{2}+S_{5}), (S_{1}+S_{2},S_{1}+S_{6})\}\).
First, suppose that \((H_{1},H_{2})\in \{(S_{3},S_{7}),(S_{3},S_{3}+S_{4})\}\). Since \(S_{3}\) can be decomposed into \(S_{1},S_{2}\) and \(S_{7}\) can be decomposed into \(S_{3},S_{4}\), it follows that \(S_{1}, S_2, S_3, S_{4}\) is a Ramsey Chain of length \(4\).
Next, suppose that \((H_{1},H_{2})=(S_{1}+S_{2},S_{2}+S_{5})\). Since \(S_{5}\) can be decomposed into \(S_{1},S_{2},S_{2}\), we let \(G_{1}=S_{1}\subseteq H_{2}\), \(G_{2}=S_{2} \subseteq H_{2}\), \(G_{3}=S_{1}+S_{2}= H_{1}\) and \(G_{4}=2S_{2}\subseteq H_2\), resulting in a Ramsey Chain of length \(4\) in \(H\).
Finally, suppose that \((H_{1},H_{2})=(S_{1}+S_{2},S_{1}+S_{6})\). Since \(S_{6}\) can be decomposed into \(S_{1},S_{2},S_{3}\), we let \(G_{1}= S_{1}\subseteq H_{2}\), \(G_{2}=S_{2} \subseteq H_{2}\), \(G_{3}=S_{1}+S_{2}= H_{1}\), and \(G_{4}=S_{1}+S_{3}\subseteq H_{2}\), resulting in a Ramsey Chain of length \(4\) in \(H\).
Case 4. \((m_{1},m_{2})=(4,6)\). In this case, \((H_{1}, H_{2}) \in \{(S_{4}, 2S_{3}), (S_{1}+S_{3}, S_{2}+S_{4}), (S_{1}+S_{3},S_{6}), (2S_{2},S_{1}+S_{5})\}\).
First, suppose that \((H_{1}, H_{2})\in \{(S_{4},2S_{3}), (S_{1}+S_{3}, S_{2}+S_{4}), (S_{1}+S_{3},S_{6})\}\). Since \(S_{3}\) can be decomposed into \(S_{1},S_{2}\) and \(S_{6}\) can be decomposed into \(S_{2}, S_{4}\), it follows that \(S_{1}, S_2, S_3, S_{4}\) is a Ramsey Chain of length \(4\) in \(H\).
Next suppose that \((H_1, H_2)=(2S_{2},S_{1}+S_{5})\). Since \(S_{5}\) can be decomposed into \(S_{1},S_{2},S_{2}\), we let \(G_{1}=S_{1}\subseteq H_{2}\), \(G_{2}=S_{2}\subseteq H_{2}\), \(G_{3}=S_{1}+S_{2}\subseteq H_{2}\), and \(G_{4}=2S_{2}=H_{1}\), resulting a Ramsey Chain of length \(4\) in \(H\).
Case \(5\). \((m_{1},m_{2})=(5,5)\). Thus, \((H_{1},H_{2}) \in \{(S_{5},S_{3}+S_{2}),(S_{1}+S_{4},S_{2}+S_{3}),(S_{2}+S_{3},S_{1}+S_{4}),(S_{2}+S_{3},S_{5})\}\). Since \(S_{5}\) can be decomposed into \(S_{1},S_{4}\), it follows that \(S_{1}, S_2, S_3, S_{4}\) is a Ramsey Chain of length \(4\) in \(H\).
Therefore, \(AR(H) = 4\) and so \(AR(S_3+S_{m-3}) = 4\) for \(10 \le m \le 14\). ◻
For \(2\)-galaxies \(S_3+S_{m-3}\) of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k\ge 5\), we obtain the following result as a consequence of Observations 2.1 and 2.2, Proposition 3.2, and Theorem 3.6.
Corollary 3.8. Let \(H= S_3+S_{m-3}\) be a \(2\)-galaxy of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k\ge 5\). If \(m \ne {k+1\choose 2}+1\), then \[AR(H)= \left\{\begin{array}{cl} k-1 & \mbox{ if $m={k+1 \choose 2}$},\\[.2cm] k & \mbox{ if ${k+1 \choose 2} + 2\le m < {k+2 \choose 2}$}. \end{array} \right.\]
Proof. By Proposition 3.2, if \(m={k+1\choose 2}\), then \(AR(H)=k-1\) (since \(3 \le k-2\) when \(k \ge 5\)); while if \({k+1\choose 2} +3\le m < {k+2\choose 2}\), then \(AR(H)=k\). Thus, we may assume that \(m= {k+1\choose 2}+2\). Let \(H' = S_2 +S_{m-3}\). Then \(H' \subseteq H\). Since the size of \(H'\) is \(m-1= {k+1\choose 2}+1\), it follows by Theorem 3.6 that \(AR(H') = k\). Consequently, \(AR(H) \ge AR(H') = k\) by Observations 2.1. Therefore, \(AR(H) = k\) by Observation 2.2. ◻
Based on all \(2\)-galaxies \(S_3+S_{m-3}\) of size \(m\) where \(m = {k+1\choose 2}+1\) for some integer \(k\ge 5\) whose Ramsey indexes have been determined, we arrive at the following conjecture.
Conjecture 3.9. If \(H= S_3+S_{m-3}\) is a \(2\)-galaxy of size \(m= {k+1\choose 2}+1\) for some integer \(k\ge 5\), then \(AR(H) = k\).
Conjecture 3.9 has been verified for small values of \(k\). In particular, \(AR(S_3+S_{13})= 5\) where \(k = 5\) and \(AR(S_3+S_{19})= 6\) where \(k = 6\). Furthermore, the proof of Proposition 3.7 can be extended to show that if \(c\) is a red-blue coloring of \(S_3+S_{m-3}\) of size \(m= {k+1\choose 2}+1\) with red subgraph of size \(m_1\) and blue graph of size \(m_2\) such that \(m_1 \le m_2\) and \(1 \le m_1 \le 5\), then \(AR_c(S_3+S_{m-3}) = k\).
For 2-galaxies \(H = S_x + S_{m-x}\) of size \(m\) where \(4 \le x \le \frac{m}{2}\) and \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k \ge 4\), it follows by Proposition 3.2 that \[AR(H)= \left\{\begin{array}{cl} k-1 & \mbox{ if $m={k+1 \choose 2}$ and $x \le k-2$},\\[.2cm] k & \mbox{ if ${k+1 \choose 2} + x\le m < {k+2 \choose 2}$}. \end{array} \right.\]
What remains unknown are Ramsey indexes of those 2-galaxies \(H = S_x + S_{m-x}\) of size \(m\) where \(4 \le x \le \frac{m}{2}\) and \({k+1 \choose 2} + 1 \le m \le {k+1 \choose 2} + (x-1)\). For example, consider \(S_4 + S_{m-4}\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k \ge 4\). It can be shown that
(1) for \(k = 4\), if \({4+1\choose 2} = 10 \le m< 15 = {4+2\choose 2}\), then \(AR(S_4+S_{m-4}) = 4\),
(2) for \(k = 5\), if \({5+1\choose 2} = 15 \le m< 21 = {5+2\choose 2}\), then \(AR(S_4+S_{m-4}) =5\), and
(3) for \(k = 6\), if \(m = {6+1 \choose 2} = 21\), then \(AR(S_4+S_{m-4}) = 5\); while if \({6+1 \choose 2} + 1= 22 \le m < 28={6+2 \choose 2}\), then \(AR(S_4+S_{m-4}) = 6\).
As a result of Proposition 3.3, Theorem 3.6, Corollary 3.8 as well as all 2-galaxies that have been encountered so far, we are led to the following conjecture.
Conjecture 4.1. If \(H\) is a \(2\)-galaxy of size \(m\) where \({k+1\choose 2} \le m < {k+2\choose 2}\) for some integer \(k \ge 4\), then
\((1)\) \(AR(H) = k\) if \({k+1\choose 2} < m < {k+2\choose 2}\) and
\((2)\) \(AR(H) = k-1\) or \(AR(H) = k\) if \(m = {k+1\choose 2}\).
We are grateful to Professor Gary Chartrand for suggesting the concepts and problems to us and kindly providing useful information on this topic. Furthermore, we thank the anonymous referee whose valuable suggestions resulted in an improved paper.