In this paper, we consider Ramsey and Gallai-Ramsey numbers for a generalized fan \(F_{t,n}:=K_1+nK_t\) versus triangles. Besides providing some general lower bounds, our main results include the evaluations of \(r(F_{3,2}, K_3)=13\) and \(gr(F_{3,2}, K_3, K_3)=31\).
In this paper, we consider Ramsey and Gallai-Ramsey numbers for generalized fans versus complete graphs, primarily focusing of the case of triangles (i.e., \(K_3\)-subgraphs). In order to describe our main results, we must first introduce the terminology and background needed for our investigation. For \(t\ge 1\), a \(t\)-coloring of a graph \(G\) is a map \[f:E(G)\longrightarrow \{1, 2, \dots , t\},\] which is not assumed to be surjective. To help with visualizing arguments, we will refer to the colors \(1\), \(2\), and \(3\) as red, blue, and green, respectively. The (\(t\)-color) Ramsey number \(r(G_1, G_2, \dots , G_t)\) is the least \(p\in \mathbb{N}\) such that every \(t\)-coloring of the complete graph \(K_p\) of order \(p\) contains a subgraph that is isomorphic to \(G_i\) in color \(i\), for some \(i\in \{1, 2, \dots , t\}\). If \(G_1=G_2=\cdots =G_t\), then we shorten the notation for the corresponding Ramsey number to \(r^t(G_1)\). The current state-of-knowledge on Ramsey numbers can be found in the dynamic survey [19].
A \(t\)-coloring \(f\) of a graph \(G\) is called a Gallai \(t\)-coloring if it does not contain any rainbow triangles. In other words, \[|\{f(xy), f(xz), f(yz)\}|\le 2, \quad \mbox{for all distinct $x, y, z\in V(G)$}.\]
The (\(t\)-color) Gallai-Ramsey number \(gr(G_1, G_2, \dots , G_t)\) is the least \(p\in \mathbb{N}\) such that every Gallai \(t\)-coloring of \(K_p\) contains a subgraph that is isomorphic to \(G_i\) in color \(i\), for some \(i\in \{1, 2, \dots , t\}\). If \(G_1=G_2=\dots = G_t\), then we shorten the notation for the corresponding Gallai-Ramsey number to \(gr^t(G_1)\). Note that if \(t\in \{1,2\}\), then \(gr(G_1)=r(G_1)=|V(G_1)|\) and \(gr(G_1, G_2)=r(G_1, G_2)\). A fundamental tool for working in Gallai-Ramsey theory is the following structure theorem for Gallai-colorings, which reinterprets a classic result of Gallai [9].
Theorem 1.1 ([9, [12]).Every Gallai-colored complete graph can be formed by replacing the vertices of a \(2\)-colored complete graph of order at least \(2\) with Gallai-colored complete graphs.
In this theorem, the \(2\)-colored complete graph is called the base graph and the Gallai-colored complete graphs that replace the vertices in the base graph are called the blocks. This partitioning of vertices into blocks is referred to as a Gallai partition. To clarify the statement of this theorem, consider a \(t\)-coloring \(f\) of a graph \(G\) and a \(t\)-coloring \(g\) of a graph \(H\), using the same collection of colors. If a vertex \(x\in V(G)\) is replaced by \(H\), then the resulting graph has vertex set \((V(G)-\{x\})\cup V(H)\). Its edge set consists of the edges \(uv\in E(G)\) with \(u,v\in V(G)-\{ x \}\) (colored according to \(f\)), edges \(yz\in E(H)\), with \(y,z\in V(H)\) (colored according to \(g\)), and edges \(vz\) with \(v\in V(G)-\{x\}\) and \(z\in V(H)\) such that \(vx\in E(G)\) (colored the same as \(vx\) according to \(f\)).
A \(2\)-coloring of a graph \(G\) is called a connected \(2\)-coloring of \(G\) if the subgraphs spanned by the edges in each of the colors are connected. The connected Ramsey number \(r_c(G_1, G_2)\) is the least \(p\in \mathbb{N}\) such that every connected \(2\)-coloring of \(K_p\) contains a subgraph isomorphic to \(G_i\) in color \(i\), for some \(i\in \{1,2\}\) (see [21]). Since every connected \(2\)-coloring of \(K_p\) is a \(2\)-coloring of \(K_p\), it follows that \[r_c(G_1, G_2)\le r(G_1, G_2),\] for all graphs \(G_1\) and \(G_2\). A \(t\)-coloring of a graph \(G\) is called a rainbow \(t\)-coloring if every vertex in \(G\) is incident with an edge in each of the \(t\)-colors. Note that every connected \(2\)-coloring of a graph \(G\) is a rainbow \(2\)-coloring of \(G\), but the converse is not true.
We denote by \(P_n\) and \(C_n\) the path and cycle of order \(n\), respectively. For any graph \(G\), we write \(nG\) for the disjoint union of \(n\) copies of \(G\). If \(G_1\) and \(G_2\) are any two graphs, then the join of \(G_1\) and \(G_2\), denoted \(G_1+G_2\), is the graph formed by taking the disjoint union of \(G_1\) and \(G_2\) and adding in all edges \(xy\) such that \(x\in V(G_1)\) and \(y\in V(G_2)\). The complete bipartite graph \(K_{m,n}\) is defined by \(K_{m,n}:=mK_1+nK_1\) and the generalized fan \(F_{t,n}\) is defined by \(F_{t,n}:=K_1+nK_t\). In \(F_{t,n}\), the \(K_1\)-subgraph is called the center, and the \(K_t\)-subgraphs are called the blades. Note that \(F_{t,n}\) has order \(tn+1\), size \(n{t+1\choose 2}\), and clique number \(t+1\). When \(t=1\), the graph \(F_{1,n}=K_{1,n}\) is called a star, and when \(t=2\), the graph \(F_n:=F_{2,n}\) is called a fan.
The lower bound for Gallai-Ramsey numbers that is given in the next theorem was proved in Lemma 2.1 of [3]. It generalizes the lower bound of Chvátal and Harary [7]: \[r(G_1, G_2)\ge (|V(G_1)|-1)(\chi(G_2)-1)+1,\label{CHbound} \tag{1}\] where \(\chi (G_2)\) is the chromatic number of \(G_2\) and \(G_1\) is assumed to be connected.
Theorem 1.2 ([3]).Let \(t\ge 2\) and assume that \(n_i\ge 2\) for all \(i\in \{2, 3, \dots , t\}\). Then for any connected graph \(G\), \[gr(G, K_{n_2}, \dots, K_{n_t})\ge (|V(G)|-1)(gr(K_{n_2}, \dots , K_{n_t})-1)+1.\]
The first nontrivial Gallai-Ramsey number to be evaluated was due to Chung and Graham [6], where they proved a result equivalent to the following theorem.
Theorem 1.3 ([6]).For all \(t\ge 1\), \[gr^t(K_3)=\left\{\begin{array}{ll} 5^{t/2}+1 & \mbox{if $t$ is even} ,\\ 2\cdot 5^{(t-1)/2}+1 & \mbox{if $t$ is odd.} \end{array}\right.\]
From Theorems 1.2 and 1.3, it follows that \[gr(F_{t,n},\underbrace{K_3, \dots , K_3}_{\mbox{$s$ terms}})\ge \left\{ \begin{array}{ll} tn\cdot 5^{s/2}+1 & \mbox{if $s$ is even}, \\ 2tn\cdot 5^{(s-1)/2}+1 & \mbox{if $s$ is odd,}\end{array}\right.\label{mainlower} \tag{2}\] for all \(t\ge 2\) and \(s\ge 1\).
Our main results include the evaluations of \(r(F_{3,2}, K_3)=13\) and \(gr(F_{3,2}, K_3, K_3)=31\) in Theorems 2.1 and 3.6, respectively. Additionally, we offer some directions for future related work and a conjecture regarding the Gallai-Ramsey number for a generalized fan versus triangles.
In 2018, Hao and Lin [13] proved that \[r(F_{3,n}, K_3)=6n+1, \quad \mbox{for all $n\ge 3$.}\]
In particular, their evaluation did not include the Ramsey number \(r(F_{3,2}, K_3)\), which we will need to prove Theorem 3.6 in Section 3. So, we determine this Ramsey number in the next theorem.
Theorem 2.1. \(r(F_{3,2},K_3) = 13\).
Proof. The lower bound \(r(F_{3,2}, K_3) \ge 13\) follows from inequality (1). To show that \(13\) is an upper bound, consider a \(2\)-coloring of \(K_{13}\) (using red and blue) that avoids a blue \(K_3\). We break the proof into cases based upon the possible degree of a vertex with respect to each color.
Case 1. Suppose that there exists a vertex \(x\) that is incident with at least \(8\) red edges (and at most \(4\) blue edges). Without loss of generality, assume that the edges \(xa_1, xa_2, \dots , xa_8\) are red. Since \(r(2K_3, K_3)=8\) [4] it follows that the subgraph induced by \(\{a_ 1, a_2, \dots, a_8\}\) contains a red \(2K_3\). This red \(2K_3\), along with vertex \(x\), forms a red \(F_{3,2}\).
Case 2. Suppose that there exists a vertex \(y\) that is incident with at least \(7\) blue edges (and at most \(5\) red edges). Without loss of generality, assume that the edges \(yb_1, yb_2, \dots , yb_7\) are blue. Since a blue \(K_3\) is avoided, the subgraph induced by \(\{b_1, b_2, \dots , b_7\}\) is a complete red subgraph, which necessarily contains a red \(F_{3,2}\).
Case 3. Suppose that there exists a vertex \(z\) that is incident with exactly \(6\) red edges (and exactly \(6\) blue edges). Without loss of generality, assume that \(za_1, za_2,\dots, za_6\) are red and \(zb_1, zb_2,\dots , zb_6\) are blue. Since a blue \(K_3\) is avoided, the subgraph induced by \(\{b_1, b_2, \dots , b_6\}\) is a red \(K_6\). If any \(a_i\), where \(i\in \{1, 2, \dots , 6\}\), joins to at least three of \(b_1, b_2, \dots ,b_6\) with red edges, then a red \(F_{3,2}\) can be formed with \(a_i\) being a vertex in one of the blades. So, each of \(a_1, a_2, \dots, a_6\) joins to at least four of \(b_1, b_2, \dots , b_6\) with blue edges. By the pigeonhole principle, for any distinct \(i,j\in \{1, 2, \dots , 6\}\), the edge \(a_ia_j\) must join with at least one of \(b_1, b_2, \dots , b_6\) using only blue edges. Avoiding a blue \(K_3\) then forces the subgraph induced by \(\{z, a_1, a_2, \dots , a_6\}\) to be a red \(K_7\), which necessarily contains a red \(F_{3,2}\).
Case 4. Suppose that every vertex is incident with exactly \(7\) red edges and \(5\) blue edges. This case cannot occur as the subgraph spanned by either color would contain an odd number of vertices with odd degree.
In each case, we have shown that if a blue \(K_3\) is avoided, there must exist a red \(F_{3,2}\). It follows that \(r(F_{3,2},K_3)\le 13\). ◻
In order to evaluate \(gr(F_{3,2}, K_3, K_3)\) (Theorem 3.6), we begin by proving several lemmas that will be needed. The first involves a simple generalization of Lemma 1 of [4].
Lemma 3.1. \(gr(2K_3, K_3, K_3)\le 14\).
Proof. Consider a Gallai \(3\)-coloring of \(K_{14}\) that lacks a blue \(K_3\) and lacks a green \(K_3\), and let \(V\) denote the vertex set. Since \(gr^3(K_3)=11\) [6], it follows that there exists a red \(K_3\), whose vertices we label by \(a\), \(b\), and \(c\). The subgraph induced by \(V-\{a, b, c\}\) is a Gallai \(3\)-coloring of \(K_{11}\), so once again, it must contain a red \(K_3\). Since we have shown the existence of a red \(2K_3\), it follows that \(gr(2K_3, K_3, K_3)\le 14\). ◻
Lemma 3.2. Let \(p\ge 8\) and consider a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). Also, assume that the Gallai partition for this coloring has a base graph \(\mathcal{B}\) with a rainbow \(2\)-coloring in colors red and blue. Then each block in the Gallai-partition contains at most \(7\) vertices.
Proof. Let \(f\) be a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and green \(K_3\). If the base graph \(\mathcal{B}\) of a Gallai-partition of \(f\) is a rainbow \(2\)-coloring of \(\mathcal{B}\) (using red and blue), then no block can contain any blue edges without forming a blue \(K_3\). If a block \(X\) contains at least \(8\) vertices, then \(r(2K_3, K_3)=8\) [4] implies that it contains a red \(2K_3\) or a green \(K_3\). In the former case, the red \(2K_3\) along with any vertex in a block joined by a red edge to \(X\) will form a red \(F_{3,2}\). Thus, no block contains more than \(7\) vertices. ◻
Lemma 3.3. Let \(p\ge 9\) and consider a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). Also, assume that the Gallai partition for this coloring has a base graph \(\mathcal{B}\) with a rainbow \(2\)-coloring in colors red and blue. If \(\mathcal{B}\) contains a red \(K_2\)-subgraph, then the blocks that correspond with the vertices in the red \(K_2\)-subgraph contain at most \(8\) vertices in total.
Proof. Let \(f\) be a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and green \(K_3\). If the base graph \(\mathcal{B}\) in a Gallai-partition of \(f\) is a rainbow \(2\)-coloring of \(\mathcal{B}\) (using red and blue), then no block can contain any blue edges. Assume that \(\mathcal{B}\) contains a red \(K_2\) whose blocks contain at least \(9\) vertices in total. From Lemma 3.2, it follows that each block in the red \(K_2\) contains at most \(7\) vertices and at least \(2\) vertices. Consider the following three cases.
Case 1. Assume that in the red \(K_2\) in \(\mathcal{B}\), one of the blocks (call it \(X\)) has order at least \(7\) while the other block (call it \(Y\)) has order \(2\). By Theorem 1 of [10], the block of order at least \(7\) contains at least two red \(K_3\)-subgraphs. If the two red \(K_3\)-subgraphs are vertex-disjoint, then along with any vertex in \(Y\), a red \(F_{3,2}\) is formed. So, assume two red vertex disjoint \(K_3\)-subgraphs do not exist. By Proposition 2.1 of [5], every \(2\)-coloring of \(K_7\) contains two edge-disjoint monochromatic \(K_3\)-subgraphs. It follows that \(X\) contains a red \(F_2\). Label its center vertex \(a\), the vertices in one blade \(b\) and \(c\) , and the vertices in its other blade \(d\) and \(e\). Label two vertices in \(Y\) by \(f\) and \(g\). See Image (a) in Figure 1.
Then a red \(F_{3,2}\) is formed with center vertex \(a\), vertices \(b\), \(c\), and \(f\) forming one blade, and \(d\), \(e\), and \(g\) forming the other blade.
Case 2. Assume that in the red \(K_2\) in \(\mathcal{B}\), one of the blocks (call it \(X\)) has order at least \(6\) while the other block (call it \(Y\)) has order \(3\). Similar to the previous case, \(X\) contains at least two red \(K_3\)-subgraphs by Theorem 1 of [10]. If the two red \(K_3\)-subgraphs are disjoint or have a single vertex in common, then a red \(F_{3,2}\) can be formed following the rationale given in Case 1. So, assume the two red \(K_3\)-subgraphs in \(X\) have an edge in common. Label the vertices in the common edge \(a\) and \(b\), and the other vertices in the red \(K_3\)-subgraphs by \(c\) and \(d\). In the block \(Y\), at least one red edge must exist in order to avoid a green \(K_3\). Label the vertices in a red edge by \(e\) and \(f\), and label the other vertex in \(Y\) by \(g\). See Image (b) in Figure 1. Then a red \(F_{3,2}\) is formed with center vertex \(a\), one blade with vertices \(c\), \(e\), and \(f\), and the other blade with vertices \(b\), \(d\), and \(g\).
Case 3. Assume that in the red \(K_2\) in \(\mathcal{B}\), one of the blocks (call it \(X\)) has order at least \(5\) while the other block (call it \(Y\)) has order at least \(4\). Among all possible \(2\)-colorings of \(Y\) (red/green colorings of \(K_4\)) that lack a green \(K_3\), there must exist a red \(P_3\) or a red \(2K_2\). This leads to two subcases.
Subcase 3.1. Suppose that \(Y\) contains a red \(P_3\) given by \(abc\). Since \(r(2K_2, K_3)=5\) [7], block \(X\) must contain a red \(2K_2\). Label the vertices in one \(K_2\) by \(d\) and \(e\) and the vertices in the other \(K_2\) by \(f\) and \(g\). See Image (c) in Figure 1. Then a red \(F_{3,2}\) is formed with center vertex \(b\), one blade with vertices \(a\), \(d\) and \(e\), and the other blade with vertices \(c\), \(f\), and \(g\).
Subcase 3.2. Suppose that \(Y\) contains a red \(2K_2\) with one \(K_2\) having vertices \(a\) and \(b\) and the other \(K_2\) having vertices \(c\) and \(d\). Since \(r(P_3, K_3)=5\) [7], it follows that \(X\) has a red \(P_3\), which we label by \(efg\). See Image (d) in Figure 1. Then a red \(F_{3,2}\) is formed with center vertex \(f\), one blade with vertices \(a\), \(b\), and \(e\), and the other blade with vertices \(c\), \(d\), and \(g\).
As this takes care of all cases where each of the blocks in the red \(K_2\)-subgraph contain at least \(2\) vertices individually, and at least \(9\) vertices in total, it follows that at most \(8\) vertices total is needed to avoid a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). ◻
Lemma 3.4. Let \(p\ge 8\) and consider a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). Also, assume that the Gallai partition for this coloring has a base graph \(\mathcal{B}\) with a rainbow \(2\)-coloring in colors red and blue. If \(\mathcal{B}\) contains a red \(K_3\)-subgraph, then the blocks that correspond with the vertices in the red \(K_3\)-subgraph contain at most \(7\) vertices in total.
Proof. Let \(f\) be a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and green \(K_3\). If the base graph \(\mathcal{B}\) in a Gallai-partition of \(f\) is a rainbow \(2\)-coloring of \(\mathcal{B}\) (using red and blue), then no block can contain any blue edges. Assume that \(\mathcal{B}\) contains a red \(K_3\) whose blocks contain at least \(8\) vertices in total. From Lemma 3.2, it follows that each block in the red \(K_3\) contains at most \(7\) vertices and at least \(1\) vertex. We consider the following three cases.
Case 1. Suppose that some block (call it \(X\)) has order at least \(6\), and the other two blocks (call them \(Y\) and \(Z\)) each contain a single vertex. Label the vertices in \(Y\) and \(Z\) by \(y\) and \(z\), respectively. Since \(\mathcal{B}\) has a rainbow \(2\)-coloring in red and blue, no blue edge exists in \(X\). By Theorem 1 of [10], \(X\) contains at least two monochromatic \(K_3\)-subgraphs, both of which must be red. If the two red \(K_3\)-subgraphs are disjoint, then a red \(F_{3,2}\) can be formed with the vertex \(y\) as the center and the red \(K_3\)-subgraphs in \(X\) as the blades. If the two red \(K_3\)-subgraphs in \(X\) share a single vertex (assume that their vertex sets are \(\{a,b,c\}\) and \(\{a, d, e\}\)), then a red \(F_{3,2}\) can be formed with \(a\) as the center, one blade formed by \(b\), \(c\), and \(y\), and the other blade formed by \(d\), \(e\), and \(z\). The only other possibility is that the two \(K_3\)-subgraphs in \(X\) share an edge (assume that their vertex sets are \(\{a, b, c\}\) and \(\{a, b, d\}\), and the other two vertices in \(X\) are given by \(e\) and \(f\)). See Image (a) in Figure 2.
If \(ef\) is red, then a ref \(F_{3,2}\) is formed with \(z\) as the center, one blade formed by \(e\), \(f\), and \(y\), and the other blade formed by \(a\), \(b\), and \(c\). If \(ef\) is green, then at least one of \(ce\) and \(cf\) must be red. Without loss of generality, suppose that \(ce\) is red. Then a red \(F_{3,2}\) is formed with \(z\) as the center, one blade formed by \(a\), \(b\), and \(d\), and the other blade formed by \(c\), \(e\), and \(y\).
Case 2. Suppose that some block (call it \(X\)) has order at least \(5\), one block (call it \(Y\)) has a single vertex (which we denote by \(y\)), and the other block (call it \(Z\)) contains two vertices (which we denote by \(z\) and \(w\)). Since \(r(2K_2, K_3)=5\) [7], it follows that \(X\) contains a red \(2K_2\). Let \(ab\) and \(cd\) be disjoint red edges in \(X\) (see Image (b) of Figure 2). Then a red \(F_{3,2}\) is formed with center \(y\), one blade formed by \(a\), \(b\), and \(w\), and the other blade formed by \(c\), \(d\), and \(z\).
Case 3. Suppose that some block (call it \(X\)) has order at least \(4\), and that the other two blocks (call them \(Y\) and \(Z\)) each have order \(2\). Denote the vertices in \(Y\) by \(y\) and \(u\) and the vertices in \(Z\) by \(z\) and \(w\). If \(X\) contains a red \(K_3\)-subgraph, call its vertices \(a\), \(b\), and \(c\) (see Image (c) of Figure 2). Then a red \(F_{3,2}\) is formed with center \(a\), one blade formed by \(b\), \(u\), and \(w\), and the other blade formed by \(c\), \(y\), and \(z\). If \(X\) lacks a red \(K_3\)-subgraph, then it must contain a red \(2K_2\), whose edges we denote by \(ab\) and \(cd\) (see Image (d) of Figure 2). Then a red \(F_{3,2}\) is formed with center \(z\), one blade formed by \(a\), \(b\), and \(u\), and the other blade formed by \(c\), \(d\), and \(y\).
Case 4. Suppose that two blocks contain at least \(3\) vertices (call them \(X\) and \(Y\)) and the other block (call it \(Z\)) has order \(2\). Denote the vertices in \(Z\) by \(w\) and \(z\) and note that each of \(X\) and \(Y\) must contain a red edge. Without loss of generality, suppose that \(a\), \(b\), and \(c\) are in \(X\) with \(ab\) red and that \(d\), \(e\), and \(f\) are in \(Y\) with \(de\) red (see Image (e) of Figure 2). Then a red \(F_{3,2}\) is formed with center \(z\), one blade formed by \(a\), \(b\), and \(f\), and the other blade formed by \(c\), \(d\), and \(e\).
As this takes care of all cases where the blocks in the red \(K_3\)-subgraph contain at least \(8\) vertices in total, it follows that at most \(7\) vertices total is needed to avoid a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). ◻
Lemma 3.5. Let \(p\ge 8\) and consider a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). Also, assume that the Gallai partition for this coloring has a base graph \(\mathcal{B}\) with a rainbow \(2\)-coloring in colors red and blue. If \(\mathcal{B}\) contains a red \(K_4\)-subgraph, then the blocks that correspond with the vertices in the red \(K_4\)-subgraph contain at most \(7\) vertices in total.
Proof. Let \(f\) be a Gallai \(3\)-coloring of \(K_p\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and green \(K_3\). If the base graph \(\mathcal{B}\) in a Gallai-partition of \(f\) is a rainbow \(2\)-coloring of \(\mathcal{B}\) (using red and blue), then no block can contain any blue edges. Assume that \(\mathcal{B}\) contains a red \(K_4\) whose blocks contain at least \(8\) vertices in total.
Case 1. Suppose that at most one block (call it \(W\)) contains a single vertex. Denote the other blocks by \(X\), \(Y\), and \(Z\). Let \(w\in V(W)\), \(a,b\in V(X)\), \(c,d\in V(Y)\), and \(e,f\in V(Z)\) (see Image (a) of Figure 3).
Then a red \(F_{3,2}\) is formed with \(w\) as the center, one blade formed by \(a\), \(c\), and \(e\), and the other blade formed by \(b\), \(d\), and \(f\)
Case 2. Suppose that exactly two blocks (call them \(W\) and \(X\)) have only one vertex each. Let \(w\in V(W)\) and \(x\in V(X)\). Denote the other blocks by \(Y\) and \(Z\). At least one of \(Y\) and \(Z\) must contain at least three vertices. Suppose that \(a,b\in V(Y)\) and \(c,d,e\in V(Z)\). Note that \(Z\) must contain at least one red edge. Without loss of generality, suppose that \(cd\) is red (see Image (b) of Figure 3). Then a red \(F_{3,2}\) is formed with \(w\) as the center, one blade given by \(a\), \(c\), and \(d\), and the other blade given by \(x\), \(b\), and \(e\).
Case 3. Suppose that three blocks (call them \(W\), \(X\), and \(Y\)) contain only a single vertex. Let \(w\in V(W)\), \(x\in V(X)\), and \(y\in V(Y)\). Denote the other block by \(Z\) and assume that \(a,b,c,d,e\in V(Z)\). Since \(r(2K_2, K_3)=5\) [7], \(Z\) contains a red \(2K_2\), which we assume is given by \(ab\) and \(cd\) (see Image (c) of Figure 3). Then a red \(F_{3,2}\) is formed with center \(w\), one blade formed by \(x\), \(a\), and \(b\), and the other blade formed by \(y\), \(c\), and \(d\).
As this takes care of all cases where the blocks in the red \(K_3\)-subgraph contain at least \(8\) vertices in total, it follows that at most \(7\) vertices total is needed to avoid a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). ◻
With the preliminary lemmas now proved, we are ready to move on to the main result of the paper.
Theorem 3.6. \(gr(F_{3,2},K_{3},K_{3}) = 31\).
Proof. The lower bound \(gr(F_{3,2}, K_3, K_3)\ge 31\) follows from Inequality (2). To prove the upper bound, consider a Gallai \(3\)-coloring of \(K_{31}\) that lacks a blue \(K_3\) and a green \(K_3\). The theorem will follow by proving that such a coloring contains a red \(F_{3,2}\). In a Gallai partition for this coloring, assume that the base graph \(\mathcal{B}\) is chosen to have minimal order. By Theorem 1.1 and Lemma 3.1 of [17], \(|V(\mathcal{B})|\ge 2\) and \(|V(\mathcal{B})|\ne 3\). As \(\mathcal{B}\) is \(2\)-colored, \(|V(\mathcal{B})|\le 12\) by Theorem 2.1. We break the remainder of the proof into cases, based on the order of \(\mathcal{B}\).
Case 1. Assume that \(|V(\mathcal{B})|=2\). By the pigeonhole principle, one of the blocks must have order at least \(16\). If the edge in \(\mathcal{B}\) is red, then since \(gr(2K_3, K_3, K_3)\le 14\) (Lemma 3.1), the block with order at least \(16\) contains a red \(2K_3\). A red \(2K_3\) along with any vertex from the other block forms a red \(F_{3,2}\). If the edge in \(\mathcal{B}\) is blue, then neither of the two blocks contains a blue edge without forming a blue \(K_3\). Since \(r(F_{3,2}, K_3)=13\) (Theorem 2.1), the block with order at least \(16\) contains a red \(F_{3,2}\).
Case 2. Assume that \(|V(\mathcal{B})|=4\). Note that \(\mathcal{B}\) is \(2\)-colored and if any vertex in \(\mathcal{B}\) is incident with edges that all have the same color, then the blocks corresponding with the other vertices can be grouped together into a single block, contradicting the assumption regarding the minimal order of \(\mathcal{B}\). Thus, each vertex in \(\mathcal{B}\) is incident with edges in both colors (i.e., \(\mathcal{B}\) has a rainbow \(2\)-coloring). We now consider subcases based on which two colors appear in \(\mathcal{B}\).
Subcase 2.1. Assume that the edges in \(\mathcal{B}\) are red and (without loss of generality) blue. Since every vertex in \(\mathcal{B}\) is incident with edges in both colors, no blue edge can exist in any block without forming a blue \(K_3\). By the pigeonhole principle, some block must have order at least \(8\). Since \(r(2K_3, K_3)=8\) [4], such a block contains a red \(2K_3\), and the vertex in \(\mathcal{B}\) corresponding with this block is incident with a red edge. Selecting any vertex from a block that is red-adjacent to the block containing the red \(2K_3\) forms a red \(F_{3,2}\).
Subcase 2.2. Assume that the edges in \(\mathcal{B}\) are blue and green. Then no blue or green edge exists in any block without forming a blue \(K_3\) or a green \(K_3\). As some block has order at least \(8\), it contains a red \(K_8\), which contains \(F_{3,2}\) as a subgraph.
Case 3. Assume that \(|V(\mathcal{B})|=5\). Similar to Case 2, every vertex in \(\mathcal{B}\) is incident with edges in both of the colors that appear in \(\mathcal{B}\). We again have two subcases, based on which colors are in \(\mathcal{B}\).
Subcase 3.1. Suppose that the edges in \(\mathcal{B}\) are red and (without loss of generality) blue. Since \(r(2K_2, K_3)=5\) [7], \(\mathcal{B}\) contains a red \(2K_2\). In total, the blocks corresponding with the red \(2K_2\) contain at most \(16\) vertices by Lemma 3.3. The other block contains at most \(7\) vertices by Lemma 3.2. Thus, in total there are at most \(23\) vertices, from which we see that this case does not occur without producing a red \(F_{3,2}\).
Subcase 3.2. Suppose that the edges in \(\mathcal{B}\) are blue and green. If a blue \(K_3\) and green \(K_3\) are avoided, then no block contains blue or green edges. By the pigeonhole principle, some block must have order at least \(7\), producing a red \(K_7\), which contains \(F_{3,2}\) as a subgraph.
For the remaining cases where \(|V(\mathcal{B})|\ge 6\), note that if the base graph \(\mathcal{B}\) is colored in blue and green, then since \(r^2(K_3)=6\) [11], there exists a blue \(K_3\) or a green \(K_3\). Hence, for the remainder of the proof, we will assume that \(\mathcal{B}\) is colored with red and (without loss of generality) blue. Also, the \(2\)-coloring of \(\mathcal{B}\) is necessarily a connected \(2\)-coloring. Otherwise, the components in the subgraph spanned by edges in the disconnected color can be grouped together into blocks, contradicting the minimal assumption on the order of \(\mathcal{B}\). One consequence of this observation is that every vertex in \(\mathcal{B}\) is incident with both red and blue edges (i.e., \(\mathcal{B}\) has a rainbow \(2\)-coloring).
Case 4. Assume that \(|V(\mathcal{B})|=6\). Since \(r^2(K_3)=6\) [11], it follows that there is a red \(K_3\)-subgraph in \(\mathcal{B}\). By Lemma 3.4, the three blocks corresponding with the vertices in the red \(K_3\) contain at most \(7\) vertices in total. Each of the other three blocks contain at most \(7\) vertices by Lemma 3.2, leading to a total of at most \(28\) vertices, from which it follows that this case does not occur without producing a red \(F_{3,2}\).
Case 5. Assume that \(|V(\mathcal{B})|=7\). By Proposition 2.1 of [5], \(\mathcal{B}\) contains at least two edge disjoint red \(K_3\)-subgraphs. If the two red \(K_3\) subgraphs are vertex-disjoint, then the six blocks corresponding with their vertices contain at most \(14\) vertices in total by Lemma 3.4. The block not included in the two vertex-disjoint red \(K_3\)-subgraphs contains at most \(7\) vertices by Lemma 3.2. Thus, in total, there are at most \(21\) vertices, from which we see that this case does not occur. So, assume that the two edge-disjoint red \(K_3\)-subgraphs share a single vertex in \(\mathcal{B}\) (forming a red \(F_2\)). If we consider one of the red \(K_3\)-subgraphs, the blocks corresponding to its vertices contain at most \(7\) vertices in total by Lemma 3.4. The other two vertices in the red \(F_2\) form a red \(K_2\), from which it follows that the corresponding blocks contain at most \(8\) vertices in total by Lemma 3.3. By Lemma 3.2, the other two blocks each contain at most \(7\) vertices, leading to a total of \(29\) vertices. Thus, this case does not occur without producing a red \(F_{3,2}\).
Case 6. Assume that \(|V(\mathcal{B})|=8\). By Proposition 2.2 of [5], \(\mathcal{B}\) contains two vertex-disjoint red \(K_3\)-subgraphs. The six blocks corresponding with the two red \(K_3\)-subgraphs contain at most \(14\) vertices in total by Lemma 3.4. Each of the other two blocks contain at most \(7\) vertices by Lemma 3.2. This results in a total of at most \(28\) vertices, from which it follows that this case does not occur without producing a red \(F_{3,2}\).
Case 7. Assume that \(|V(\mathcal{B})|=9\). By Proposition 2.2 of [5], \(\mathcal{B}\) contains two vertex-disjoint red \(K_3\)-subgraphs and the six blocks corresponding with the two red \(K_3\)-subgraphs contain at most \(14\) vertices in total by Lemma 3.4. At least one red edge must exist in \(\mathcal{B}\) among the three vertices not in the red \(2K_3\). The two blocks corresponding to such a red edge contain at most \(8\) vertices by Lemma 3.3. The block corresponding to the last vertex in \(\mathcal{B}\) then contains at most \(7\) vertices by Lemma 3.2. This results in at most a total of at most \(29\) vertices, from which it follows that this case does not occur without producing a red \(F_{3,2}\).
Case 8. Assume that \(|V(\mathcal{B})|=10\). Since \(r(K_4, K_3)=9\) [11], \(\mathcal{B}\) contains a red \(K_4\). The blocks corresponding to the red \(K_4\) contain at most \(7\) vertices by Lemma 3.5. The vertices in \(\mathcal{B}\) that are not in the red \(K_4\) must contain a red \(K_3\) since \(r(K_3, K_3)=6\) [11]. The blocks corresponding with the red \(K_3\) contain at most \(7\) vertices in total by Lemma 3.4. Among the three vertices in \(\mathcal{B}\) that are not in the red \(K_4\) or the red \(K_3\), at least one red edge must exist, and the blocks corresponding to that red \(K_2\) contain at most \(8\) vertices in total by Lemma 3.3. The one remaining vertex in \(\mathcal{B}\) corresponds with a block that contains at most \(7\) vertices by Lemma 3.2. Thus, in total there are at most \(29\) vertices, from which it follows that this case does not occur without producing a red \(F_{3,2}\).
Case 9. Assume that \(|V(\mathcal{B})|=11\). Since \(r(K_4, K_3)=9\) [11], \(\mathcal{B}\) contains a red \(K_4\), and the blocks corresponding to the red \(K_4\) contain at most \(7\) vertices by Lemma 3.5. The vertices in \(\mathcal{B}\) that are not in the red \(K_4\) must contain a red \(K_3\) since \(r(K_3, K_3)=6\) [11], and the blocks corresponding with the red \(K_3\) contain at most \(7\) vertices in total by Lemma 3.4. This leaves four vertices remaining in \(\mathcal{B}\) that are not in the red \(K_4\) or the red \(K_3\). The red subgraph of \(\mathcal{B}\) induced by these four vertices either contain a red \(K_3\) or a red \(2K_2\). If a red \(K_3\) is formed, then the blocks corresponding with the red \(K_3\) contain at most \(7\) vertices in total by Lemma 3.4 and the last block contains at most \(7\) vertices by Lemma 3.2, leading to a total of at most \(28\) vertices. If a red \(2K_2\) is formed, then the blocks corresponding with each red \(K_2\) contain at most \(8\) vertices in total by Lemma 3.3, leading to a total of at most \(30\) vertices. In both subcases, we see this case does not occur without producing a red \(F_{3,2}\).
Case 10. Assume that \(|V(\mathcal{B})|=12\). This final case requires us to use the connected Ramsey number \(r_c(K_{1,6}, K_3)=11\) (see [8] and [18]), from which it follows that \(\mathcal{B}\) contains a red \(K_{1,6}\). Hence, there exists a block \(U\) corresponding with a vertex in \(\mathcal{B}\) that is incident with at least \(6\) red edges and at most \(10\) red edges.
Subcase 10.1. Suppose that \(U\) corresponds with a vertex in \(\mathcal{B}\) that has red-degree \(6\) and blue degree \(5\). Let \(V\), \(W\), \(X\), \(Y\), and \(Z\) be the blocks in \(\mathcal{B}\) that join to \(U\) via blue edges and note that the subgraph of \(\mathcal{B}\) induced by the vertices corresponding with these blocks form a red \(K_5\) in \(\mathcal{B}\). By Lemma 3.5, the blocks \(V\), \(W\), \(X\), and \(Y\) contain a total of at most \(7\) vertices. At least one of \(V\), \(W\), \(X\), and \(Y\) (say, \(V\)) contains only a single vertex. Then by Lemma 3.5, the blocks \(W\), \(X\), \(Y\), and \(Z\) contain at most a total of \(7\) vertices. Since \(gr(2K_3, K_3, K_3)\le 14\) by Lemma 3.1, the blocks that are red-adjacent to \(U\) contain at most \(13\) vertices in total. The block \(U\) contains at most \(7\) vertices by Lemma 3.2, from which it follows that there are at most \(28\) vertices in total. So, this subcase does not occur without producing a red \(F_{3,2}\)
Subcase 10.2. Suppose that \(U\) corresponds with a vertex in \(\mathcal{B}\) that has red-degree at least \(7\). By Lemmas 3.2, 3.3, 3.4, and 3.5, the blocks in \(\mathcal{B}\) that are blue-adjacent to \(U\) contain at most \(8\) vertices in total. Lemma 3.2 implies that \(U\) contains at most \(7\) vertices and Lemma 3.1 implies that the blocks that are red-adjacent to \(U\) contain at most \(13\) vertices in total. It follows that there are at most a total of \(28\) vertices, from which we see that this subcase does not occur without producing a red \(F_{3,2}\).
In all cases, we have shown that a Gallai \(3\)-coloring of \(K_{31}\) contains a red \(F_{3,2}\), a blue \(K_3\), or a green \(K_3\). It follows that \(gr(F_{3,2},K_{3},K_{3}) \le 31\), completing the proof of the theorem. ◻
We conclude by describing some directions for future work, and by stating a conjecture motivated by our results. Besides considering Ramsey and Gallai-Ramsey numbers for generalized fans versus complete graphs with order larger than \(3\), one may also consider the star-critical analogues of the numbers we have investigated.
We denote by \(K_n\sqcup K_{1,k}\) the graph formed by adding exactly \(k\) additional edges into the disjoint union of \(K_n\) and a single vertex \(v\). The star-critical Ramsey number \(r_*(G_1, G_2, \dots , G_t)\) is then defined to be the least nonnegative \(k\in \mathbb{Z}\) such that every \(t\)-coloring of \[K_{r(G_1, G_2, \dots , G_t)-1}\sqcup K_{1,k},\] contains a subgraph that is isomorphic to \(G_i\) in color \(i\), for some \(i\in \{1, 2, \dots , t\}\). Star-critical Ramsey numbers were first introduced by Hook [14] and were further developed in [15] (see [1] for a thorough overview). Restricting our attention to Gallai \(t\)-colorings, the star-critical Gallai-Ramsey number \(gr_*(G_1, G_2, \dots , G_t)\) can be defined analogously. Su and Liu [20] were the first to define star-critical Gallai-Ramsey numbers, which were further considered in [2] and [3]. We reserve the evaluations of \(r_*(F_{3,2}, K_3)\) and \(gr_*(F_{3,2}, K_3, K_3)\) for future study.
Known Ramsey and Gallai-Ramsey numbers for fans (and generalized fans) versus triangles (see [3], [13], and [16]) support the following general conjecture, which states that inequality (2) is exact.
Conjecture 4.1. For all \(t\ge 2\) and \(s\ge 1\), \[gr(F_{t,n},\underbrace{K_3, \dots , K_3}_{\mbox{$s$ terms}})= \left\{ \begin{array}{ll} tn\cdot 5^{s/2}+1 & \mbox{if $s$ is even} ,\\ 2tn\cdot 5^{(s-1)/2}+1 & \mbox{if $s$ is odd.}\end{array}\right.\]