Recently, it was shown that the Gallai-Ramsey number satisfies \(gr(F_{3,2}, K_3, K_3)=31\), where \(F_{3,2}\) is the generalized fan \(F_{3,2}:=K_1+2K_3\). In this paper, we show that the star-critical Gallai-Ramsey number satisfies \(gr_*(F_{3,2}, K_3, K_3)=27\). We also prove that the critical colorings for \(r_*(K_3, K_3)\), \(gr(F_{3,2},K_3,K_3)\), and \(gr_*(F_{3,2},K_3,K_3)\) are unique.
A \(t\)-coloring of a graph \(G\) is a map \(f:E(G)\longrightarrow \{1, 2, \dots , t\}\). When \(f\) satisfies \[|\{f(xy), f(xz), f(yz)\}|\le 2,\label{triangle} \tag{1}\] for all distinct \(x,y,z\in V(G)\), it is called a Gallai \(t\)-coloring. For graphs \(G_1, G_2, \dots , G_t\), the Ramsey number \(r(G_1, G_2, \dots, G_t)\) is the least \(p\in \mathbb{N}\) such that every \(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\}\). A critical coloring for \(r(G_1, G_2, \dots, G_t)\) is a \(t\)-coloring of \(K_{r(G_1, G_2, \dots, G_t)-1}\) that lacks a monochromatic copy of \(G_i\) in color \(i\), for all \(i\in \{1, 2, \dots ,t\}\). If we replace “\(t\)-coloring” with “Gallai \(t\)-coloring” and “\(r(G_1, G_2, \dots, G_t)\)” with “\(gr(G_1, G_2, \dots , G_t)\)” in these definitions, we obtain the defintions of the Gallai-Ramsey number \(gr(G_1, G_2, \dots, G_t)\) and a critical coloring for \(gr(G_1, G_2, \dots, G_t)\).
Star-critical Ramsey numbers were first introduced by Hook and Isaak (see [9] and [10]) in 2010 and measure the number of edges that one must add between a vertex and a critical coloring for a Ramsey number in order for the Ramsey property to be established. To be precise, denote by \(K_n\sqcup K_{1,k}\) the graph formed by taking the disjoint union of \(K_n\) and \(K_1\) and joining them together using exactly \(k\) edges. The star-critical Ramsey number \(r_*(G_1, G_2, \dots, G_t)\) is then defined to be the least \(k\) such that every \(t\)-coloring of \(K_{r(G_1, G_2, \dots, G_t)-1}\sqcup K_{1,k}\) contains a monochromatic copy of \(G_i\) in color \(i\), for some \(i\in \{1, 2, \dots, t\}\). Here, \[0\le r_*(G_1, G_2, \dots, G_t)\le r(G_1, G_2, \dots, G_t)-1,\] with \(r_*(G_1, G_2, \dots , G_t)\ne 0\) when every \(G_i\) lacks an isolated vertex. A critical coloring for \(r_*(G_1, G_2, \dots , G_t)\) is a \(t\)-coloring of \[K_{r(G_1, G_2, \dots, G_t)-1}\sqcup K_{1,r_*(G_1, G_2, \dots, G_t)-1},\] that lacks a monochromatic copy of \(G_i\) in color \(i\), for all \(i\in \{1, 2, \dots,t\}\).
The concept of a star-critical Ramsey number was first extended to Gallai \(t\)-colorings by Su and Liu [12] in 2022. The star-critical Gallai-Ramsey number \(gr_*(G_1, G_2, \dots, G_t)\) is the least \(k\) such that every Gallai \(t\)-coloring of \(K_{gr(G_1, G_2, \dots, G_t)-1}\sqcup K_{1,k}\) contains a monochromatic copy of \(G_i\) in color \(i\), for some \(i\in \{1, 2, \dots, t\}\). A critical coloring for \(gr_*(G_1, G_2, \dots , G_t)\) is a Gallai \(t\)-coloring of \[K_{gr(G_1, G_2, \dots, G_t)-1}\sqcup K_{1,gr_*(G_1, G_2, \dots, G_t)-1},\] that lacks a monochromatic copy of \(G_i\) in color \(i\), for all \(i\in \{1, 2, \dots,t\}\). Note that when \(t=2\), \[gr(G_1, G_2)=r(G_1, G_2) \quad \mbox{and} \quad gr_*(G_1, G_2)=r_*(G_1, G_2).\]
For \(t\ge 2\) and \(n\ge 2\), the generalized fan \(F_{t,n}\) is defined by \(F_{t,n}:=K_1+nK_t\), where \(G_1+G_2\) denotes the join of \(G_1\) and \(G_2\). It has order \(tn+1\) and minimum degree \(t\).
The Gallai-Ramsey number \(gr(F_{3,2}, K_3, K_3)=31\) was recently determined in [2]. In this paper, we build upon this result, first showing that there exist unique critical colorings for both \(r_*(K_3, K_3)\) and \(gr(F_{3,2}, K_3, K_3)\) in Section 2. In Section 3, we turn our attention to the evaluation of \(gr_*(F_{3,2}, K_3, K_3)\) and also prove that it has a unique critical coloring. Additional results involve general lower bounds for other related star-critical Gallai-Ramsey numbers and we offer a conjecture concerning the expected value of \(gr_*(F_{t,n}, K_3, K_3, \dots, K_3)\).
When all of the arguments are complete graphs, it can be shown that \[gr_*(K_{n_1}, K_{n_2}, \dots , K_{n_t})=gr(K_{n_1}, K_{n_2}, \dots , K_{n_t})-1, \label{complete} \tag{2}\] (cf. [5] and Theorem 1.1 of [1]). It is well-known that the only critical coloring for \(r(K_3, K_3)=6\) is the \(2\)-coloring of \(K_5\) whose subgraphs spanned by edges in each color form a \(C_5\) (i.e., a cycle of length \(5\)). In the next theorem, we prove that \(r_*(K_3, K_3)=5\) has a unique critical coloring.
Theorem 2.1. Up to isomorphism, the coloring shown in Figure 1 is the unique critical coloring for \(r_*(K_3, K_3)\).
Proof. Let \(V=\{a,b,c,d,e,f\}\) be the vertex set for a \(2\)-colored \(K_5\sqcup K_{1,4}\) in which \(ab\) is the “missing” edge and a monochromatic \(K_3\)-subgraph is avoided. Consider the subgraph induced by \(V\setminus\{b\}\) and note that if any vertex is incident with at least three edges of the same color, then the vertices at the other ends of those edges induce a subgraph containing an edge of the same color, or all three edges are the other color. Either way, a monochromatic \(K_3\)-subgraph is formed. Thus, every vertex is incident with exactly two red edges and exactly two blue edges.
Without loss of generality, assume that \(ac\) and \(af\) are red and \(ad\) and \(ae\) are blue. Avoiding a monochromatic \(K_3\)-subgraph then requires \(cf\) to be blue and \(de\) to be red. Now \(c\) must join to one of \(d\) and \(e\) with a red edge and the other with a blue edge. Without loss of generality, suppose that \(cd\) is red and \(ce\) is blue. Then \(ef\) must be red and \(fd\) must be blue. So, \(acdefa\) forms a red \(C_5\) and \(adfcea\) forms a blue \(C_5\).
Now consider the possibility that \(bc\) is blue. Then \(bf\) and \(be\) must be red, and \(\{b,e, f\}\) induces a red \(K_3\). It follows that \(bc\) must be red, \(bd\) must be blue, \(bf\) must be red, and \(be\) must be blue, resulting in the coloring shown in Figure 1. ◻
When \(t=3\), we will represent colors \(1\), \(2\), and \(3\), by red, blue, and green, respectively. The critical coloring for \(gr(F_{3,2}, K_3, K_3)=31\) that was given in [2] was formed by taking the unique critical coloring for \(r(K_3, K_3)\) (a \(K_5\) containing a blue \(C_5\) and a green \(C_5\)) and replacing each of its vertices with a red \(K_6\)-subgraph (see Figure 2). We refer to this critical coloring for \(gr(F_{3,2}, K_3, K_3)\) as \(\mathcal{G}\).
Before we prove that \(\mathcal{G}\) is unique, recall the well-known structure theorem for Gallai colorings, which reinterprets a classic result of Gallai [7].
Theorem 2.2([8]). 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.
The \(2\)-colored complete graph in Theorem 2.2 is called the base graph for the Gallai coloring, and the Gallai-colored complete graphs that replace the vertices in the base graph are called the blocks.
Proving that \(\mathcal{G}\) is unique will require us to consider the concept of a connected Ramsey number. 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 [13]). 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\), with exceptions for the cases where \(r(G_1, G_2) \leq 3\) (see [13]).
Theorem 2.3. Up to isomorphism, \(\mathcal{G}\) is the only critical coloring for \(gr(F_{3,2}, K_3, K_3)\).
Proof. It was shown in Theorem 3.6 of [2] that \(gr(F_{3,2}, K_3, K_3) = 31\). We must show that, up to isomorphism, \(\mathcal{G}\) is the only Gallai \(3\)-coloring of \(K_{30}\) that avoids a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). The proof of \(gr(F_{3,2}, K_3, K_3)\le 31\) given in [2] considered a Gallai \(3\)-coloring of \(K_{31}\), and then used Theorem 2.2 to break the proof into ten cases, based on the order of the base graph \(\mathcal{B}\) for the Gallai coloring, which was chosen to have minimal order. In most of the cases, it was shown that avoiding a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\) resulted in a Gallai \(3\)-coloring of a complete graph that contained at most \(29\) vertices. The only cases that allowed for up to \(30\) vertices were Subcase \(3.2\) (\(|V(\mathcal{B})|=5\) with the edges in \(\mathcal{B}\) being blue and green) and Case \(9\) (\(|V(\mathcal{B})|=11\)), so those are the only cases we must conisder here.
When \(|V(\mathcal{B})|=5\) and the edges in \(\mathcal{B}\) are blue and green, then \(\mathcal{B}\) must consist of a blue \(C_5\) and a green \(C_5\), corresponding with the unique critical coloring for \(r(K_3, K_3)\). If any block contains a blue or green edge, then a blue or green \(K_3\) can be formed. So, each block must be a red complete graph. If a block contains \(7\) or more vertices, then a red \(K_7\) contains a red \(F_{3,2}\) as a subgraph. It follows that each block is a red \(K_6\), resulting in the critical coloring \(\mathcal{G}\).
Now suppose that \(|V(\mathcal{B})|=11\). Note that \(\mathcal{B}\) cannot be blue and green as \(r(K_3, K_3)=6\) would then force there to be a blue \(K_3\) or a green \(K_3\). So, assume that \(\mathcal{B}\) is red and (without loss of generality) blue. Also, the red/blue coloring of \(\mathcal{B}\) must be a connected \(2\)-coloring, otherwise the Gallai partition can be reduced to a partition with a smaller order base graph, which has already been handled. Since \(r_c(K_{1,6}, K_3)=11\) (see [6] and [11]), some vertex \(v\) in \(\mathcal{B}\) has red degree at least \(6\) and blue degree at most \(4\). Also note that \(v\) must be incident with at least one red and one blue edge since the \(2\)-coloring of \(\mathcal{B}\) is connected.
Since a blue \(K_3\) is avoided, the vertices in \(\mathcal{B}\) that are blue adjacent to \(v\) form a red complete subgraph. By Lemmas 3.2-3.5 of [2], the blocks corresponding to these vertices contain a total of at most \(8\) vertices. Since \(r(2K_3, K_3, K_3)\le 14\) (see Lemma 1 of [2]), the blocks correponding to the vertices that are red-adjacent to \(v\) contain a total of at most \(13\) vertices. Finally, Lemma 3.2 of [2] implies that the block corresponding to vertex \(v\) contains at most \(7\) vertices. In total, the complete graph has at most \(29\) vertices, contradicting the assumption that it was a \(K_{30}\). Hence, this case does not occur.
Thus, the only critical coloring for \(gr(F_{3,2}, K_3, K_3)\) is the construction that corresponds with \(\mathcal{G}\). ◻
In the next section, we turn our attention to the evaluation of the star-critical Gallai-Ramsey number \(gr_*(F_{3,2}, K_3, K_3)\).
In this section, we prove that \(gr_*(F_{3,2}, K_3, K_3)=27\) and that the critical coloring for \(gr_*(F_{3,2}, K_3, K_3)\) is unique. First, we consider lower bounds for a more general class of Gallai-Ramsey numbers. In [2], it was noted that the Gallai-Ramsey number \[gr^s(K_3):=gr(\underbrace{K_3, K_3, \dots , K_3}_{\mbox{$s$ terms}})=\left\{\begin{array}{ll} 5^{s/2}+1 & \mbox{if $s$ is even}, \\ 2\cdot 5^{(s-1)/2}+1 & \mbox{if $s$ is odd,} \end{array}\right.\] for all \(s\ge 1\) (due to Chung and Graham [4]), along with a general lower bound from [3], implies that \[gr(F_{t,n},\underbrace{K_3, 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{3}\] for all \(t\ge 2\) and \(s\ge 1\). When this inequality gives the exact value of the Gallai-Ramsey number, we obtain the following lower bound for the corresponding star-critical Gallai-Ramsey number.
Theorem 3.1. For any \(t\ge 2\), \(n\ge 2\), and \(s\ge 1\) for which the inequality given in (3) is exact, the corresponding star-critical Gallai-Ramsey number satisfies \[gr_*(F_{t,n}, \underbrace{K_3, K_3, \dots , K_3}_{\mbox{$s$ terms}})\ge \left\{ \begin{array}{ll} tn(5^{s/2-1}-1)+t & \mbox{if $s$ is even}, \\ tn(2\cdot 5^{(t-1)/2}-1)+t & \mbox{if $s$ is odd.}\end{array}\right.\]
Proof. By Eq. (2), There exists an \(s\)-coloring of \(K_{gr^s(K_3)}-e\) that avoids a monochromatic copy of \(K_3\) in colors \(2, 3, \dots , s+1\). Denote its vertex set by \(\{x_1, x_2, \dots, x_{gr^s(K_3)}\}\) and assume that \(x_1x_2\) is the missing edge. For example, the \(s=2\) case is shown in Image (A) of Figure 3.
Replace each of the vertices \(x_2, x_3, \dots , x_{gr^s(K_3)}\) with \(K_{tn}\)-subgraphs in color \(1\). Join exactly \(t-1\) edges in color \(1\) from \(x_1\) to the block that replaced \(x_2\) (see Image (B) of Figure 3). Now, no \(F_{t,n}\) exists in color \(1\) since the color \(1\) blocks do not contain enough vertices, and the color \(1\) degree of \(x_1\) is not large enough for it to be included in an \(F_{t,n}\). We have also avoided a monochromatic copy of \(K_3\) in colors \(2, 3, \dots , s+1\). If \(s\) is even, then \[gr_*(F_{3,2}, K_3, K_3)>tn5^{s/2}-tn+(t-1).\]
If \(s\) is odd, then \[gr_*(F_{3,2}, K_3, K_3)> 2tn5^{(s-1)/2}-tn+ (t-1),\] resulting in the inequality given in the statement of the theorem. ◻
Theorem 3.2.The star-critical Gallai-Ramsey number satisfies \[gr_*(F_{3,2}, K_3, K_3)=27.\]
Proof. Theorem 3.1 (and in particular, Image (B) in Figure 3) implies that \(gr_*(F_{3,2}, K_3,\\ K_3)\ge 27\). To prove the reverse inequality, consider a Gallai \(3\)-coloring of \(K_{30}\sqcup K_{1,27}\) and let \(v\) be the vertex of degree \(27\). If we remove vertex \(v\), and assume that the resulting \(K_{30}\) avoids a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\), then by Theorem 2.3, it is the unique critical coloring \(\mathcal{G}\).
We can add at most two red edges from \(v\) to a single block in \(\mathcal{G}\), as adding three red edges from \(v\) to a single block forces a red \(F_{3,2}\). Since \(v\) joins to \(\mathcal{G}\) with \(27\) edges, \(v\) must join to each block with at least three edges. If a red \(F_{3,2}\) is avoided, then \(v\) joins to every block in \(\mathcal{G}\) with either a blue or green edge. Suppose that \(vx_1\), \(vx_2\), \(vx_3\), \(vx_4\), and \(vx_5\) are blue or green edges, where each \(x_i\) comes from a different block in \(\mathcal{G}\). Then the subgraph induced by \(\{v, x_1, x_2, x_3, x_4, x_5\}\) is a blue/green \(K_6\). Since \(r(K_3, K_3)=6\), there is a blue \(K_3\) or a green \(K_3\). It follows that \(r_*(F_{3,2}, K_3, K_3)\le 27\). ◻
Image (B) of Figure 3 provided the lower bound for \(gr_*(F_{3,2}, K_3, K_3)\) in Theorem 3.2. We refer to the graph in this image as \(\mathcal{G}'\). In the next theorem, we prove that \(\mathcal{G}'\) is the unique critical coloring for the star-critical Gallai-Ramsey number \(gr_*(F_{3,2}, K_3, K_3)\).
Theorem 3.3. Up to isomorphism, \(\mathcal{G}'\) is the only critical coloring for \(gr_*(F_{3,2}, K_3, K_3)\).
Proof. Consider a Gallai \(3\)-coloring of \(K_{30}\sqcup K_{1,26}\) that lacks a red \(F_{3,2}\), a blue \(K_3\), and a green \(K_3\). Let \(v\) be the vertex of degree \(26\). If we remove \(v\), then we have a Gallai \(3\)-coloring of \(K_{30}\) that is a critical coloring for \(gr(F_{3,2}, K_3, K_3)\). By Theorem 2.3, it is isomorphic to \(\mathcal{G}\). If \(vx_1\), \(vx_2\), \(vx_3\), \(vx_4\), and \(vx_5\) are all blue and green edges with each \(x_i\) coming from a different block in \(\mathcal{G}\), then the subgraph induced by \(\{v, x_1, x_2, x_3, x_4, x_5\}\) is a blue/green \(K_6\). The Ramsey number \(r(K_3, K_3)=6\) then implies that there is a blue \(K_3\) or a green \(K_3\). So, some block can only join to \(v\) via red edges. Since joining \(v\) to a block with three or more red edges leads to a red \(F_{3,2}\), it follows that exactly two red edges from \(v\) join to a single block (with the other four edges to that block being the missing edges) and \(v\) joins to all other blocks with six edges each.
Denote the block that joins to \(v\) with two red edges (and four missing edges) by \(Y\) and denote the other blocks in \(\mathcal{G}\) by \(X_1, X_2, X_3, X_4\). If \(v\) joins to any \(X_i\) with a red edge, then \(vx_ix_j\) is a rainbow triangle when \(x_j\in V(X_j)\) and \(i\ne j\). Select \(y\in V(Y)\) such that \(vy\) is a missing edge and select \(x_i\in V(X_i)\), for each \(i\in \{1, 2, 3, 4\}\) such that \(vx_i\) is either blue or green. Then the subgraph induced by \(\{v, y, x_1, x_2, x_3, x_4\}\) is a critical coloring for \(r_*(K_3, K_3)\). By Theorem 2.1, \(vx_i\) receives the same color as edge \(yx_i\). Thus, the critical coloring for \(gr_*(F_{3,2}, K_3, K_3)\) must be isomorphic to \(\mathcal{G}'\). ◻
In [2], it was conjectured that \[gr(F_{t,n},\underbrace{K_3, 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.\]
If this is true, then Theorems 3.1 and 3.2 support the following conjecture regarding the corresponding star-critical Gallai-Ramsey number.
Conjecture 4.1. For all \(t\ge 2\) and \(s\ge 1\), \[gr_*(F_{t,n}, \underbrace{K_3, K_3, \dots , K_3}_{\mbox{$s$ terms}})= \left\{ \begin{array}{ll} tn(5^{s/2-1}-1)+t & \mbox{if $s$ is even}, \\ tn(2\cdot 5^{(t-1)/2}-1)+t & \mbox{if $s$ is odd.}\end{array}\right.\]
The methods used in this paper and [2] may assist in proving specific cases of these two conjectures, but they do not appear to be strong enough to prove the conjectures in general.