Let \(F_n:=K_1+nK_2\) be a fan of order \(2n+1\). For \(1\le s<t\), we consider the weakened Gallai-Ramsey number \(gr^t_s(F_n)\), defined to be the least \(p\in \mathbb{N}\) such that every Gallai \(t\)-coloring of \(K_p\) contains a subgraph isomorphic to \(F_n\) whose edges use at most \(s\) colors. Our main results include the evaluations \(gr^t_2(F_2)=t+3\), \(gr^3_2(F_3)=9\), and \(gr^t_{2n-1}(F_n)=2n+1\).
Let \(nK_2\) denote a matching of size \(n\), which is defined to be the disjoint union of \(n\) edges. Given two graphs \(G_1\) and \(G_2\), the join \(G_1+G_2\) is the graph with vertex set \(V(G_1)\cup V(G_2)\) and edge set \[E(G_1)\cup E(G_2)\cup \{xy \ | \ x\in V(G_1) \ \mbox{and} \ y\in V(G_2)\}.\]
For \(n\in \mathbb{N}\), the fan \(F_n\) is defined by \(F_n:=K_1+nK_2\). From this definiton, we see that \(|V(F_n)|=2n+1\) and \(|E(F_n)|=3n\). Note that \(F_1=K_3\). In the definition of \(F_n\), the \(K_1\)-subgraph is called the center of the fan, and the \(K_2\)-subgraphs in the matching \(nK_2\) are called the blades of the fan. The path of order \(n\) will be denoted by \(P_n\) and is a sequence of \(n\) distinct vertices \(x_1x_2\cdots x_n\) such that each consecutive pair of vertices form an edge.
A \(t\)-coloring of a complete graph \(K_n\) of order \(n\) is a map \[f:E(K_n)\longrightarrow \{1 ,2, \dots , t\}.\]
For graphs \(G_1, G_2, \dots , G_t\), the \(t\)-color Ramsey number \(r(G_1, G_2, \dots , G_t)\) is defined to be the least \(p\in \mathbb{N}\) such that every \(t\)-coloring of \(K_p\) contains a monochromatic subgraph in color \(i\) that is isomorphic to \(G_i\), for some \(i\in \{1, 2, \dots , t\}\). When \(G_1=G_2=\dots =G_t\), we shorten the notation to \(r^t(G_1)\). Ramsey numbers involving fans have been extensively studied (e.g., see [3], [5], [7], [9], [17], [18], [19], [22], [24], [25], [26], [27]).
A Gallai \(t\)-coloring of \(K_n\) is a \(t\)-coloring \(f\) of \(K_n\) that avoids rainbow triangles. Here, a rainbow triangle is a subset \(\{x, y, z\}\subseteq V(K_n)\) such that no two of \(f(xy)\), \(f(xz)\), and \(f(yz)\) are equal. For any graph \(G\), the Gallai-Ramsey number \(gr^t(G)\) is the least \(p\in \mathbb{N}\) such that every Gallai \(t\)-coloring of \(K_p\) contains a monochromatic subgraph that is isomorphic to \(G\). Since every Gallai \(t\)-coloring of \(K_p\) is a \(t\)-coloring of \(K_p\), it follows that \(gr^t(G)\le r^t(G)\) for every graph \(G\). Gallai-Ramsey numbers for fans were studied by Mao, Wang, Magnant, and Schiermeyer [21] in 2023, where they prove that \[gr^t(F_2)=\left\{ \begin{array}{ll} 9 & \mbox{if $t=2$}, \\ \frac{83}{2}\cdot 5^{(t-4)/2}+\frac{1}{2} & \mbox{if $t\ge 4$ is even} ,\\ 4\cdot 5^{(t-1)/2}+1 & \mbox{if $t$ is odd.}\end{array}\right.\]
They also showed that for \(t\ge 2\), \[gr^t(F_3)\ge \left\{ \begin{array}{ll} 14\cdot 5^{(t-2)/2}-1 & \mbox{if $t$ is even}, \\ 33\cdot 5^{(t-3)/2} & \mbox{if $t$ is odd,}\end{array}\right.\] and conjectured that these lower bounds are sharp.
In this paper, our focus will be on a “weakened” version of \(gr^t(F_n)\) in that we will seek out subgraphs isomorphic to \(F_n\) that use at most a given number of colors. To be precise, let \(1\le s<t\) and define the weakened Gallai-Ramsey number \(gr^t_s(G)\) to be the least \(p\in \mathbb{N}\) such that every Gallai \(t\)-coloring of \(K_p\) contains a subgraph that is isomorphic to \(G\) whose edges use at most \(s\) colors. This generalizes the concept of a Gallai-Ramsey number in that \(gr^t(G)=gr^t_1(G)\). For \(s_1\le s_2\), the inequality \[gr^t_{s_2}(G)\le gr^t_{s_1}(G),\] guarantees that weakened Gallai-Ramsey numbers exist. At present, weakened Gallai-Ramsey numbers have been studied for complete graphs ([1], [6], [15], and [16]), for cycles ([6] and [15]), and for wheels, books, and complete bipartite graphs [15].
One benefit of working with Gallai \(t\)-colorings of \(K_n\) (as opposed to \(t\)-colorings of \(K_n\)) is that the proofs of upper bounds for Gallai-Ramsey numbers can be broken into manageable cases by using the following structural theorem.
Theorem 1.1([12]).Every Gallai coloring of a complete graph can be formed by taking a \(2\)-colored complete graph with order at least \(2\), and replacing its vertices with Gallai-colored complete graphs.
The partitioning of the vertex set in the original complete graph into the vertex sets for the Gallai-colored complete graphs is called a Gallai partition. The \(2\)-colored complete graph with order at least \(2\) is called the base graph of the Gallai partition, and the Gallai-colored complete graphs that replace the vertices in the base graph are called the blocks of the Gallai partition. All edges joining any distinct pair of blocks are necessarily the same color. The following lemma will save us some time when using Theorem 1.1.
Lemma 1.2([20]).If \(\mathcal{B}\) is the base graph of a Gallai parition, chosen to have minimal order, then \(|V(\mathcal{B})|\ne 3\).
In Section 2, we prove that \[gr^t_2(F_2)=t+3, \quad \mbox{for all $t\ge 3$},\] \[gr^3_2(F_3)=9,\] and \[gr^t_{2n-1}(F_n)=2n+1, \quad \mbox{for all $n\ge 2$ and $t\ge 2n$.}\]
Section 3 concludes with some directions for future work on this topic.
Before we turn to the evaluation of certain weakened Gallai-Ramsey numbers for fans, we recall a couple of known Ramsey numbers. In 1967, Gerencsér and Gyárfás [11] determined the value of the \(2\)-color Ramsey number for paths. They showed that for all \(n\ge m\ge 2\), \[r(P_m, P_n)=n+\left\lfloor{\frac{m}{2}}\right\rfloor+1. \label{paths} \tag{1}\]
The Ramsey number for matchings was determined by Cockayne and Lorimer [8] in 1975. They proved that if \(n_1, n_2, \dots , n_t\in \mathbb{N}\) such that \(n_1=\max \{n_1, n_2, \dots , n_t\}\), then \[r(n_1K_2, n_2K_2, \dots , n_tK_2)=n_1+1+\mathop{\sum}\limits_{i=1}^{t} (n_i-1).\label{CL} \tag{2}\]
In particular, \(r^t(nK_2)=n(t+1)-t+1\). In the following theorem, we determine \(gr^t_2(F_2)\).
Theorem 2.1. For all \(t\ge 3\), \(gr^t_2(F_2)=t+3\).
Proof. To prove the lower bound, begin with a \(K_3\) in color \(1\), introduce a new vertex \(x_1\), and color all edges from \(x_1\) to the \(K_3\) with color \(2\). Next, introduce vertex \(x_2\) and color all edges from \(x_2\) to the existing graph with color \(3\). Continue in this manner, sequentially introducing vertices \(x_3, x_4, \dots, x_{t-1}\), coloring all edges from \(x_i\) to the existing graph with color \(i+1\) (the \(t=3\) case is shown in Figure 1).
The resulting \(K_{t+2}\) avoids rainbow triangles. Every \(F_2\)-subgraph in which the center of the fan is a vertex in the \(K_3\) in color \(1\) uses at least three colors on its four edges to the blades of the fan. If an \(F_2\)-subgraph has \(x_i\) as its center and the edges to its blades are chosen to use at most two colors, then at least one of the blades must use a third color. Hence, no \(F_2\)-subgraph exists that uses at most two colors, and it follows that \(gr^t_2(F_2)\ge t+3\).
To prove the upper bound, let \(\mathcal{B}\) be the base graph, chosen to have minimal order. By Theorem 1.1 and Lemma 1.2, \(|V(\mathcal{B})|\ge 2\) and \(|V(\mathcal{B})|\ne 3\). If \(|V(\mathcal{B})|\ge 5\), then selecting a single vertex from five distinct blocks results in a \(K_5\) whose edges use at most two colors. Such a \(K_5\) contains \(F_2\) as a subgraph. We now handle the cases \(|V(\mathcal{B})|=2\) and \(|V(\mathcal{B})|=4\) separately.
Case 1. Suppose that \(|V(\mathcal{B})|=2\) and assume that the edges joining the blocks are red (color \(1\)). We consider two subcases.
Subcase 1.1. Suppose that one block only contains a single vertex \(x\). Then the larger block has order \(t+2\). If we view the colors red and blue (colors \(1\) and \(2\), respectively) as if they are the same color, then since \(gr^{t-1}(2K_2)=t+2\) by Eq. (2), the larger block contains a red/blue \(2K_2\) or a monochromatic copy of \(2K_2\) in one of the colors \(3, 4, \dots , t\). In both cases, an \(F_2\) that uses at most two colors (one of which is red) is formed with \(x\) as its center and the \(2K_2\) forming the blades.
Subcase 1.2. Suppose that both blocks have order at least \(2\). Note that one block must have order at least \(3\). Let \(x_1\) and \(x_2\) be in one block and \(y_1\), \(y_2\), and \(y_3\) be in the other block. Since rainbow triangles are avoided, at least two of the edges of the subgraph induced by \(\{y_1,y_2,y_3\}\) use the same color. Without loss of generality, suppose that \(y_1y_2\) and \(y_1y_3\) are both the same color. Then an \(F_2\)-subgraph is formed with center \(y_1\) and blades \(x_1y_2\) and \(x_2y_3\) whose edges use at most two colors, one of which is red.
Case 2. Suppose that \(|V(\mathcal{B})|=4\) and assume that the edges joining the blocks are red and blue. Denote the vertex sets for the blocks by \(W\), \(X\), \(Y\), and \(Z\). Note that one block must contain at least two vertices. Without loss of generality, assume that \(w\in W\), \(x\in X\), \(y\in Y\), and \(z_1,z_2\in Z\). Then a red/blue \(F_2\) can be formed with center \(w\) and blades \(xz_1\) and \(yz_2\).
In both cases, we find that there exists an \(F_2\) whose edges use at most two colors. It follows that \(gr^t_2(F_2)\le t+3\). ◻
Now we consider the weakened Gallai-Ramsey number \(gr^3_2(F_3)\).
Theorem 2.2. \(gr^3_2(F_3)=9\).
Proof. To prove the lower bound, start by replacing one vertex in a blue \(K_2\) with a green \(K_5\). Call the resulting blue/green coloring of \(K_6\) \(\mathcal{G}\). Here, \(\mathcal{G}\) is a critical coloring for \(r(2K_2, 3K_2)\) (see [8]). Next, take a red \(K_2\) and replace one of its vertices with a blue \(K_2\) and the other vertex with a copy of \(\mathcal{G}\) (see Figure 2).
The resulting Gallai \(3\)-coloring of \(K_8\) does not have a large enough blue/green connected component to have a blue/green \(F_3\). In order to have a red/blue \(F_3\), there would have to be a blue \(2K_2\) in the larger block. In order to have a red/green \(F_3\), there would have to be a green \(3K_2\) in the larger block. Since this Gallai \(3\)-coloring of \(K_8\) avoids an \(F_3\) whose edges use at most two colors, we obtain the inequality \(gr^3_2(F_3)\ge 9\).
To prove the reverse inequality, consider a Gallai \(3\)-coloring of \(K_9\) and let \(\mathcal{B}\) be the base graph, chosen to have minimal order. By Theorem 1.1 and Lemma 1.2, it follows that \(2\le |V(\mathcal{B})|\le 6\) and \(|V(\mathcal{B})|\ne 3\). Consider the following cases.
Case 1. Suppose that \(|V(\mathcal{B})|=2\) and that the edges joining the two blocks are red. Denote the vertex sets for the two blocks by \(X\) and \(Y\). We must consider two subcases.
Subcase 1.1. Suppose that one block has order at most \(2\). Denote its vertex set by \(X\), and denote the vertex set for the larger block by \(Y\). Note that \(|Y|\ge 7\). If the subgraph induced by \(Y\) does not contain any red edges, then it contains a blue/green \(K_7\), which contains \(F_3\) as a subgraph. So, without loss of generality, assume that \(y_1y_2\) is red, where \(y_1,y_2\in Y\). If the subgraph induced by \(Y\setminus \{y_1,y_2\}\) lacks red edges, then \(r^2(2K_2)=5\) (by Eq. (2)) implies that it contains a monochromatic \(2K_2\) that is blue or green. This \(2K_2\), along with edge \(y_1y_2\) and a vertex \(x\in X\), forms an \(F_3\) spanned by edges using at most two colors in which \(x\) is the center. So, assume that the subgraph induced by \(Y\setminus \{y_1,y_2\}\) does contain a red edge, and without loss of generality, assume that \(y_3y_4\) is one such edge. Then an \(F_3\) that uses at most two colors can be formed with center \(x\) and blades \(y_1y_2\), \(y_3y_4\), and \(y_5y_6\), where \(y_5, y_6\in Y\setminus \{y_1, y_2, y_3, y_4\}\).
Subcase 1.2. Suppose that one block has order \(3\). Denote its vertex set by \(X=\{x_1, x_2,x_3\}\) and denote the vertex set for the block of order \(6\) by \(Y=\{y_1, y_2, \dots , y_6\}\). If the subgraph induced by \(X\) contains a red edge (say, \(x_1x_2\) is red), then \(r^3(2K_2)=6\) (by Eq. (2)) implies that the subgraph induced by \(Y\) contains a monochromatic \(2K_2\). If the edges is this \(2K_2\) are given by \(y_1y_2\) and \(y_3y_4\), then an \(F_3\) whose edges use at most two colors is formed with center \(x_1\) and blades \(y_1y_2\), \(y_3y_4\), and \(x_2y_5\). So, assume that the subgraph induced by \(X\) is blue/green. At least two of the edges in this blue/green \(K_3\) must be the same color. Without loss of generality, assume that \(x_1x_2\) and \(x_1x_3\) are both blue. If the subgraph induced by \(Y\) contains a red or blue edge (say, \(y_1y_2\) is red or blue), then a red/blue \(F_3\) is formed with \(x_1\) as the center and blades \(y_1y_2\), \(x_2y_3\), and \(x_3y_4\). So, assume that the subgraph induced by \(Y\) only contains green edges. Then a red/green \(F_3\) is formed with center \(x_1\) and blades \(y_1y_2\), \(y_3y_4\), and \(y_5y_6\).
Subcase 1.3. Suppose that one block has order \(4\) and the other block has order \(5\). Without loss of generality, assume that \(X=\{x_1, x_2, x_3, x_4\}\) and \(Y=\{y_1, y_2, y_3, y_4,y_5\}\) are the vertex sets for the blocks. If the subgraph induced by \(X\) contains a red edge (say, \(x_1x_2\) is red), then if we view red and blue as the same color, \(r^2(2K_2)=5\) (by Eq. (2)) implies that the subgraph induced by \(Y\) contains a red/blue \(2K_2\) or a green \(2K_2\). If \(y_1y_2\) and \(y_3y_4\) form a red/blue \(2K_2\), then a red/blue \(F_3\) is formed with center \(x_1\) and blades \(y_1y_2\), \(y_3y_4\), and \(x_2y_5\). If \(y_1y_2\) and \(y_3y_4\) form a green \(2K_2\), then a red/green \(F_3\) can be formed with center \(x_1\) and blades \(y_1y_2\), \(y_3y_4\), and \(x_2y_5\).
So, assume that the subgraph induced by \(X\) does not contain any red edges. Since \(r^2(P_3)=3\) (by Eq. (1)), it must contain a monochromatic \(P_3\). Without loss of generality, assume that \(x_1x_2x_3\) is a blue \(P_3\). If the subgraph induced by \(Y\) contains a red or blue edge (say, \(y_1y_2\) is red or blue), then a red/blue \(F_3\) is formed with center \(x_2\) and blades \(y_1y_2\), \(x_1y_3\), and \(x_3y_4\). So, assume that all of the edges in the subgraph induced by \(Y\) are green. Then a red/green \(F_3\) is formed with center \(y_1\) and blades \(x_1y_2\), \(x_2y_3\), and \(x_3y_4\).
Case 2. Suppose that \(|V(\mathcal{B})|=4\) and that the edges in \(\mathcal{B}\) are red and blue. Denote the vertex sets for the blocks by \(W\), \(X\), \(Y\), and \(Z\). By the pigeonhole principle, some block must contain at least three vertices, and we assume it is the block with vertex set \(Z\). Consider the following subcases.
Subcase 2.1. Suppose that some block only contains a single vertex (say, \(W=\{w\}\)). If at least one of \(X\) and \(Y\) has order at least \(2\) (say, \(x_1x_2\in X\), \(y\in Y\), and \(z_1,z_2,z_3\in Z\)), then a red/blue \(F_3\) is formed with center \(w\) and blades \(x_1z_1\), \(x_2z_2\), and \(yz_3\). So, assume that \(X\) and \(Y\) both have order \(1\) and that \(X=\{x\}\), \(Y=\{y\}\), and \(Z=\{z_1, z_2, \dots, z_6\}\). If the subgraph induced by \(Z\) contains a red or blue edge (say, \(z_1z_2\) is red or blue), then a red/blue \(F_3\) is formed with center \(w\) and blades \(z_1z_2\), \(xz_3\), and \(yz_4\). So, assume that the subgraph induced by \(Z\) is a green \(K_6\). Then an \(F_3\) using at most two colors (one of which is green) is formed with center \(w\) and blades \(z_1z_2\), \(z_3z_4\), and \(z_5z_6\).
Subcase 2.2. Suppose that every block has order at least \(2\). Without loss of generality, suppose that the vertex sets for the blocks are given by \(W=\{w_1,w_2\}\), \(X=\{x_1,x_2\}\), \(Y=\{y_1,y_2\}\), and \(Z=\{z_1, z_2,z_3\}\). Then a red/blue \(F_3\) is formed with center \(w_1\) and blades \(x_1z_1\), \(x_2z_2\), and \(y_1z_3\).
Case 3. Suppose that \(|V(\mathcal{B})|=5\) and that the edges in \(\mathcal{B}\) are red and blue. Denote the vertex sets for the blocks by \(V\), \(W\), \(X\), \(Y\), and \(Z\). By the pigeonhole principle, some block has order at least \(2\), and since there are only nine vertices in total, some block has order \(1\). Without loss of generality, assume that \(V=\{v\}\). If some block has order at least \(3\) (say, \(w\in W\), \(x\in X\), \(y\in Y\), and \(z_1, z_2, z_3\in Z\)), then a red/blue \(F_3\) is formed with center \(v\) and blades \(wz_1\), \(xz_2\), and \(yz_3\). So, assume that all blocks other than \(V\) have order \(2\). If \(w_1,w_2\in W\), \(x_1, x_2\in X\), \(y_1y_2\in Y\), and \(z_1z_2\in Z\), then a red/blue \(F_3\) is formed with center \(v\) and blades \(w_1x_1\), \(w_2x_2\), and \(y_1z_1\).
Case 4. Suppose that \(|V(\mathcal{B})|=6\) and that the edges in \(\mathcal{B}\) are red and blue. Denote the vertex sets for the blocks by \(U\), \(V\), \(W\), \(X\), \(Y\), and \(Z\). By the pigeonhole principle, some block must have order at least \(2\). Without loss of generality, assume that \(u\in U\), \(v\in V\), \(w\in W\), \(x\in X\), \(y\in Y\), and \(z_1,z_2\in Z\). Then a red/blue \(F_3\) is formed with center \(u\) and blades \(vw\), \(xz_1\), and \(yz_2\).
In all cases, we have shown that a Gallai \(3\)-coloring of \(K_9\) contains an \(F_3\) that uses at most two colors. It follows that \(gr^3_2(F_3)\le 9\). ◻
In the next theorem, we consider a more general case of weakened Gallai-Ramsey numbers for fans.
Theorem 2.3. For all \(n\ge 2\) and \(t\ge 2n\), \(gr^t_{2n-1}(F_n)=2n+1\).
Proof. Since \(2n+1\) vertices are required to have an \(F_n\), it follows that \(gr^t_{2n-1}(F_n)\ge 2n+1\). We will prove the reverse inequality by induction on \(n\ge 2\). For the base case \(n=2\), consider a Gallai \(t\)-coloring of \(K_5\) and let \(\mathcal{B}\) be the base graph, chosen to have minimal order. Theorem 1.1 and Lemma 1.2 imply that \(|V(\mathcal{B})|=2\) or \(|V(\mathcal{B})|=4\). In the latter case, some block must contain at least two vertices by the pigeonhole principle. If we select two vertices from one block and a single vertex from each of the other three blocks, the subgraph induced by these five vertices is a \(K_5\) (which contains \(F_2\) as a subgraph) that uses at most three colors.
So, assume that \(|V(\mathcal{B})|=2\) with the edges joining the two blocks being red. By the pigeonhole principle, some block must contain at least three vertices. An \(F_2\) that uses at most three colors can then be formed by selecting a single vertex from the smaller block to serve as its center. We then pick four other vertices (at least three of which come from the larger block) and pair them up to form the blades. It follows that \(gr^t_3(F_2)\le 5\).
Assume that \(gr^t_{2n-3}(F_{n-1})\le 2n-1\) and consider a Gallai \(t\)-coloring of \(K_{2n+1}\). By the inductive hypothesis, there exists an \(F_{n-1}\) whose edges use at most \(2n-3\) colors. If we select two vertices not contained in the \(F_{n-1}\) and let them form an \(n^{th}\) blade, at most two more colors can be introduced since rainbow triangles are avoided. The resulting \(F_n\) is spanned by edges using at most \(2n-1\) colors, implying that \(gr^t_{2n-1}(F_n)\le 2n+1\). ◻
In particular, Theorem 2.3 implies that \(gr^t_3(F_2)=5\) and \(gr^t_{5}(F_3)=7\). By a theorem of Erdős, Simonovoits, and Sós [10], every Gallai-coloring of \(K_p\) uses at most \(p-1\) colors. So, the values of \(t\ge 2n+1\) in the previous theorem follow from the case \(gr^{2n}_{2n-1}(F_n)=2n+1\).
There are many values of \(t\), \(s\), and \(n\) that remain to be considered for \(gr^t_s(F_n)\). Besides these cases, one can consider analogous problems for generalized fans. A generalized fan \(F_{t,n}\) is defined by \(F_{t,n}:=K_1+nK_t\). It follows that \(|V(F_{t,n})|=tn+1\), \(|E(F_{t,n})|=\frac{nt(t-1)}{2}\), and \(F_n=F_{2,n}\). Ramsey theory involving \(F_{t,n}\) was studied in [3], [4], [13], and [14], and [23].
Another related problem is the determination of star-critical weakened Gallai-Ramsey numbers for fans (cf. [2]). Such numbers determine the number of edges that one must add between a vertex and the complete graph \(K_{gr^t_s(F_n)-1}\) in order to guarantee the existence of an \(F_n\) that uses at most \(s\) colors.
This work was funded by a Scholarly Development Assignment Program award from Western Carolina University during Fall 2025.