betaFeedback

WorksMathematics

The 3-Color 2-Chromatic Gallai-Ramsey Number for Complete Graphs

Abstract

For 1≤i≤j≤k1\le i\le j\le k, let gr23(Ki,Kj,Kk)gr^3_2(K_i, K_j, K_k) be the least n∈Nn\in \mathbb{N} such that every rainbow triangle-free 33-coloring of KnK_n (using red, blue, and green) contains a red/blue KiK_i, a red/green KjK_j, or a blue/green KkK_k. In this paper, we completely evaluate gr23(Ki,Kj,Kk)gr^3_2(K_i, K_j, K_k) for all values of ii, jj, and kk in which r(Ki,Kj)r(K_i,K_j) is known.

Introduction

In 1977, K. Chung, M. Chung, and C. Liu [3] proposed an interesting variation of multicolor Ramsey numbers. Rather than finding the threshold at which a monochromatic subgraph exists within a tt-colored complete graph, they sought the threshold at which a subgraph exists whose edges use at most ss colors, where 1≤s<t1 \le s < t. The chromatic Ramsey numbers they defined were some of the first “weakened” Ramsey numbers to be studied (cf. [2, 11]). In this paper, we consider chromatic Ramsey numbers for Gallai colorings (those that lack rainbow triangles). Before describing our results, we first review the necessary definitions and background.

A tt-coloring of a graph GG is a map f:E(G)⟶{1,2,…,t}f : E(G) \longrightarrow\{1,2,\ldots,t\}. Such maps are not assumed to be surjective (i.e., a tt-coloring may use fewer than tt colors). If a tt-coloring is surjective, then it is called an exact tt-coloring. If t≥2t \ge2 and G1,G2,…,GtG_1,G_2,\ldots,G_t are graphs, then the tt-color Ramsey number r(G1,G2,…,Gt)r(G_1,G_2,\ldots,G_t) is the least n∈Nn \in\mathbb{N} such that every tt-coloring of the edges of KnK_n results in a subgraph isomorphic to GiG_i in color ii, for some i∈{1,2,…,t}i \in\{1,2,\ldots,t\}. A critical coloring for r(G1,G2,…,Gt)r(G_1,G_2,\ldots,G_t) is a tt-coloring of Kr(G1,G2,…,Gt)−1K_{r(G_1,G_2,\ldots,G_t)-1} that avoids a copy of GiG_i in color ii, for all i∈{1,2,…,t}i \in\{1,2,\ldots,t\}. A detailed overview of known values of r(G1,G2,…,Gt)r(G_1,G_2,\ldots,G_t) can be found in Radziszowski’s dynamic survey [22].

2020 Mathematics Subject Classification. Primary: 05C55, 05C15; Secondary: 05D10.

Key words and phrases. Gallai coloring, chromatic Ramsey number, weakened Ramsey number.

Let Si:={1,2,…,t}∖{t+1−i}S_i:=\{1,2,\ldots,t\}\setminus\{t+1-i\}. Then the tt-color (t−1)(t-1)-chromatic Ramsey number rt−1t(G1,G2,…,Gt)r^t_{t-1}(G_1,G_2,\ldots,G_t) is defined to be the least n∈Nn\in\mathbb{N} such that every tt-coloring of KnK_n contains a copy of GiG_i spanned by edges whose colors are in the set SiS_i, for some i∈{1,2,…,t}i\in\{1,2,\ldots,t\}. A critical coloring for rt−1t(G1,G2,…,Gt)r^t_{t-1}(G_1,G_2,\ldots,G_t) is a tt-coloring of Krt−1t(G1,G2,…,Gt)−1K_{r^t_{t-1}(G_1,G_2,\ldots,G_t)-1} that lacks a GiG_i whose edges use only the colors in SiS_i, for every i∈{1,2,…,t}i\in\{1,2,\ldots,t\}. A more general class of chromatic Ramsey numbers than those defined here have also been studied in [4, 12, 13, 18, 23]. In [4], the following 3-color 2-chromatic Ramsey numbers were determined:

r23(K3,K3,Kk)={5if 3≤k≤56if k≥6,r^3_2(K_3,K_3,K_k)= \begin{cases} 5 & \text{if }3\le k\le5\\ 6 & \text{if }k\ge6, \end{cases}
r23(K3,K4,Kk)={7if k=48if 5≤k≤69if k≥7,r^3_2(K_3,K_4,K_k)= \begin{cases} 7 & \text{if }k=4\\ 8 & \text{if }5\le k\le6\\ 9 & \text{if }k\ge7, \end{cases}
r23(K3,K5,Kk)={9if k=511if k=612if 7≤k≤813if 9≤k≤1314if k≥14,r^3_2(K_3,K_5,K_k)= \begin{cases} 9 & \text{if }k=5\\ 11 & \text{if }k=6\\ 12 & \text{if }7\le k\le8\\ 13 & \text{if }9\le k\le13\\ 14 & \text{if }k\ge14, \end{cases}

and r23(K4,K4,K4)=10r^3_2(K_4,K_4,K_4)=10.

A Gallai tt-coloring of a graph GG is a tt-coloring of GG that avoids rainbow triangles. That is, every K3K_3-subgraph of GG has at most two colors on its edges. The tt-color (t−1)(t-1)-chromatic Gallai-Ramsey number grt−1t(G1,G2,…,Gt)gr^t_{t-1}(G_1,G_2,\ldots,G_t) is the least n∈Nn\in\mathbb{N} such that every Gallai tt-coloring of KnK_n contains a copy of GiG_i spanned by edges whose colors are in the set SiS_i, for some i∈{1,2,…,t}i\in\{1,2,\ldots,t\}. Since every Gallai tt-coloring of KnK_n is a tt-coloring of KnK_n, it follows that

grt−1t(G1,G2,…,Gt)≤rt−1t(G1,G2,…,Gt).gr^t_{t-1}(G_1,G_2,\ldots,G_t)\le r^t_{t-1}(G_1,G_2,\ldots,G_t).

A critical coloring for grt−1t(G1,G2,…,Gt)gr^t_{t-1}(G_1,G_2,\ldots,G_t) is a Gallai tt-coloring of Kgrt−1t(G1,G2,…,Gt)−1K_{gr^t_{t-1}(G_1,G_2,\ldots,G_t)-1} that avoids a copy of GiG_i whose edges use only the colors in SiS_i, for all i∈{1,2,…,t}i\in\{1,2,\ldots,t\}.

Our focus in this paper will be on the determination of chromatic Gallai-Ramsey numbers of the form gr23(Ki,Kj,Kk)gr^3_2(K_i,K_j,K_k), where we assume that i≤j≤ki\le j\le k, unless it is explicitly stated otherwise. We will refer to the colors 1, 2, and 3 as red, blue, and green, respectively. One benefit of working with Gallai tt-colorings of KnK_n (as opposed to tt-colorings of KnK_n) is that the proofs of upper bounds for chromatic Gallai-Ramsey numbers can be broken into manageable cases by using the following structural theorem, which is a reinterpretation of a result of Gallai [6].

Theorem 1.1 ([10]). Every Gallai-colored complete graph can be formed by replacing the vertices in a 2-colored complete graph of order at least 2 with Gallai-colored complete graphs.

In Theorem 1.1, the 2-colored complete graph with order at least 2 is called the base graph, and the Gallai-colored complete graphs that replace the vertices in the base graph are called the blocks. The following lemma will save us some time when using Theorem 1.1.

Lemma 1.2 ([19]). If BB is the base graph of a Gallai partition, chosen to have minimal order, then ∣V(B)∣≠3|V(B)| \ne3.

We will also need the following lemma that was proved by Erdős, Simonovits, and Sós [5] in 1975.

Lemma 1.3 ([5]). Every Gallai coloring of KnK_n, where n≥2n \ge2, uses at most n−1n-1 colors.

The next lemma can be compared to Lemma 5 of [1]. It follows from the observation that the addition of any vertex to a Gallai ss-colored KmK_m-subgraph introduces at most one new color to the resulting edge set.

Lemma 1.4. If a Gallai tt-coloring of KnK_n contains a KmK_m-subgraph whose edges use at most s<t−1s < t-1 colors, where m<nm < n, then it contains a Km+1K_{m+1}-subgraph whose edges use at most s+1s+1 colors.

In § 2, several general results and bounds are described that will be needed in the computation of gr23(Ki,Kj,Kk)gr^{3}_{2}(K_i,K_j,K_k). We will find that the complete evaluation of gr23(Ki,Kj,Kk)gr^{3}_{2}(K_i,K_j,K_k) is possible when r(Ki,Kj)r(K_i,K_j) is known. The known nontrivial classical 2-color Ramsey numbers are r(K3,K3)=6r(K_3,K_3)=6 [8], r(K3,K4)=9r(K_3,K_4)=9 [8], r(K3,K5)=14r(K_3,K_5)=14 [8], r(K3,K6)=18r(K_3,K_6)=18 [16], r(K3,K7)=23r(K_3,K_7)=23 [7, 15], r(K3,K8)=28r(K_3,K_8)=28 [9, 21], r(K3,K9)=36r(K_3,K_9)=36 [9, 15], r(K4,K4)=18r(K_4,K_4)=18 [8], and r(K4,K5)=25r(K_4,K_5)=25 [14, 20]. In Section 3, we focus on chromatic Gallai-Ramsey numbers of the form gr23(K3,Kj,Kk)gr^{3}_{2}(K_3,K_j,K_k), when j∈{3,4,5,6,7,8,9}j \in\{3,4,5,6,7,8,9\} and k≥jk \ge j. In § 5, we determine the values of gr23(K4,Kj,Kk)gr^{3}_{2}(K_4,K_j,K_k), when j∈{4,5}j \in\{4,5\} and k≥jk \ge j. Finally, we conclude by describing some directions for future work on this topic.

General Results for gr23(Ki,Kj,Kk)gr^{3}_{2}(K_i,K_j,K_k)

When 1≤j≤k1 \le j \le k, every complete graph contains at least one vertex, and every K1K_1 contains a red/blue K1K_1 (the colors are irrelevant since K1K_1 does not contain any edges). It follows that

gr23(K1,Kj,Kk)=1,for all 1≤j≤k.gr_2^3(K_1,K_j,K_k)=1,\qquad\text{for all }1\le j\le k.

If 2≤j≤k2\le j\le k, then gr23(K2,Kj,Kk)≥jgr_2^3(K_2,K_j,K_k)\ge j follows from considering a green Kj−1K_{j-1}, which lacks a red/blue K2K_2, a red/green KjK_j, and a blue/green KkK_k. The inequality gr23(K2,Kj,Kk)≤jgr_2^3(K_2,K_j,K_k)\le j follows from the fact that every Gallai 3-coloring of KjK_j contains a red/blue K2K_2 (that is, a red edge or a blue edge), or all edges are green, forming a red/green KjK_j. Thus,

gr23(K2,Kj,Kk)=j,for all 2≤j≤k.gr_2^3(K_2,K_j,K_k)=j,\qquad\text{for all }2\le j\le k.

The following theorem provides a general upper bound for the chromatic Gallai-Ramsey number gr23(Ki,Kj,Kk)gr_2^3(K_i,K_j,K_k), with equality when kk is sufficiently large (cf., Theorem 2.2 of [17]).

Theorem 2.1. For all 3≤i≤j≤k3\le i\le j\le k,

gr23(Ki,Kj,Kk)≤r(Ki,Kj).gr_2^3(K_i,K_j,K_k)\le r(K_i,K_j).

If k≥r(Ki,Kj)k\ge r(K_i,K_j), then

gr23(Ki,Kj,Kk)=r(Ki,Kj).gr_2^3(K_i,K_j,K_k)=r(K_i,K_j).

Proof. Let p=r(Ki,Kj)p=r(K_i,K_j) and consider a Gallai 3-coloring of KpK_p. Grouping together the colors red and blue, it follows that there exists a red/blue KiK_i or a green KjK_j (and hence, a red/green KjK_j). Therefore, gr23(Ki,Kj,Kk)≤pgr_2^3(K_i,K_j,K_k)\le p.

Now assume that k≥r(Ki,Kj)k\ge r(K_i,K_j) and let q=gr23(Ki,Kj,Kk)q=gr_2^3(K_i,K_j,K_k). Consider a blue/green coloring of KqK_q. Since it can be viewed as a Gallai 3-coloring of KqK_q, it follows that there exists a blue KiK_i (and hence, a red/blue KiK_i) or a green KjK_j (and hence, a red/green KjK_j). It follows that r(Ki,Kj)≤qr(K_i,K_j)\le q. □

This theorem also sheds some light on determining which values of gr23(Ki,Kj,Kk)gr_2^3(K_i,K_j,K_k) we can evaluate (i.e., those in which r(Ki,Kj)r(K_i,K_j) is known). The next theorem limits the rate at which gr23(Ki,Kj,Kk)gr_2^3(K_i,K_j,K_k) grows, relative to kk. Unlike elsewhere in this paper, it is not necessary to assume an ordering on ii, jj, and kk in this theorem.

Theorem 2.2. If i,j,k≥3i,j,k\ge3 and gr23(Ki,Kj,Kk−1)≤pgr_2^3(K_i,K_j,K_{k-1})\le p, then in every Gallai 3-coloring of Kp+1K_{p+1}, every vertex is incident with a red edge, or there exists a red/blue KiK_i, a red/green KjK_j, or a blue/green KkK_k.

Proof. Let gr23(Ki,Kj,Kk−1)≤pgr_2^3(K_i,K_j,K_{k-1})\le p and consider a Gallai 3-coloring of Kp+1K_{p+1}. If there exists a vertex xx that is only incident with edges that are blue and green, then deleting xx results in a Gallai 3-coloring of KpK_p. This coloring necessarily contains a red/blue KiK_i, a red/green KjK_j, or a blue/green Kk−1K_{k-1}. In the last case, including vertex xx results in a blue/green KkK_k. If no such xx exists, then every vertex is incident with a red edge. □

The Chromatic Gallai-Ramsey Number gr23(K3,Kj,Kk)gr^3_2(K_3, K_j, K_k)

We begin this section with two lemmas that provide useful upper and lower bounds for gr23(K3,Kj,Kk)gr^3_2(K_3, K_j, K_k).

Lemma 3.1. For ℓ∈N\ell\in\mathbb{N}, let j≥2ℓ+2j \ge2\ell+ 2 and

n≥r(K3,Kj−2ℓ)+2ℓ.n \ge r(K_3, K_{j-2\ell}) + 2\ell.

Then every exact Gallai 3-coloring of KnK_n that contains a red matching of size ℓ\ell must contain a red/blue K3K_3 or a red/green KjK_j.

Proof. Consider a Gallai 3-coloring of KnK_n with a red matching of size ℓ\ell. Suppose that x1x2,x3x4,…,x2ℓ−1x2ℓx_1x_2, x_3x_4, \ldots, x_{2\ell-1}x_{2\ell} are pairwise disjoint red edges and denote the other vertices by y1,y2,…,yn−2ℓy_1, y_2, \ldots, y_{n-2\ell}. If an edge xiyjx_i y_j is blue, then either the subgraph induced by {xi−1,xi,yj}\{x_{i-1}, x_i, y_j\} or the subgraph induced by {xi,xi+1,yj}\{x_i, x_{i+1}, y_j\} is a red/blue K3K_3. So, assume that all edges joining X:={x1,x2,…,x2ℓ}X := \{x_1, x_2, \ldots, x_{2\ell}\} to Y:={y1,y2,…,yn−2ℓ}Y := \{y_1, y_2, \ldots, y_{n-2\ell}\} are red or green. Since n−2ℓ≥r(K3,Kj−2ℓ)n-2\ell\ge r(K_3, K_{j-2\ell}), the subgraph induced by YY contains a blue K3K_3 (and hence, a red/blue K3K_3) or a red/green Kj−2ℓK_{j-2\ell}. In the latter case, including the vertices in XX results in a red/green KjK_j. □

Lemma 3.2. Let k≥j≥3k \ge j \ge3 and assume that 0≤ℓ<j2−10 \le\ell< \frac{j}{2} - 1 and

k≤r(K3,Kj−n)+ℓ.k \le r(K_3, K_{j-n}) + \ell.

If GG is a triangle-free graph with independence number ℓ\ell and order nn, then

gr23(K3,Kj,Kk)≥k−ℓ+n.gr^3_2(K_3, K_j, K_k) \ge k - \ell+ n.

Proof. Suppose that 0≤ℓ<j2−10 \le\ell< \frac{j}{2} - 1 and let GG be a triangle-free graph with independence number ℓ\ell and order nn. Let G\mathcal{G} be a red/green coloring of KnK_n in which the red subgraph is isomorphic to GG and the green subgraph is isomorphic to G‾\overline{G}. Since k≤r(K3,Kj−n)+ℓk \le r(K_3, K_{j-n}) + \ell, there exists a blue/green Kk−ℓ−1K_{k-\ell-1}, which we denote by H\mathcal{H}, that avoids a blue K3K_3 and a green Kj−nK_{j-n}. Take the disjoint union of G\mathcal{G} and H\mathcal{H} and join them together with green edges. By construction, no red/blue K3K_3 exists. The largest red/green complete graph that can be formed uses all of the vertices in G\mathcal{G} and the vertices from a complete green subgraph in H\mathcal{H}. Hence, it will have order at most n+j−n−1=j−1n + j - n - 1 = j - 1. The largest blue/green complete graph that can be formed uses all of the vertices in H\mathcal{H} and ℓ\ell independent vertices in the red subgraph of G\mathcal{G}. Hence, it will have order at most k−ℓ−1+ℓ=k−1k - \ell- 1 + \ell= k - 1. It follows that gr23(K3,Kj,Kk)≥k−ℓ+ngr^3_2(K_3, K_j, K_k) \ge k - \ell+ n. □

Now we are ready to focus on the evaluation of gr⁡23(K3,Kj,Kk)\operatorname{gr}_{2}^{3}(K_{3},K_{j},K_{k}), for the cases where r(K3,Kj)r(K_{3},K_{j}) is known.

Theorem 3.3. If k≥3k \ge3, then

gr⁡23(K3,K3,Kk)={kif 3≤k≤5,6if k≥6.\operatorname{gr}_{2}^{3}(K_{3},K_{3},K_{k}) = \begin{cases} k & \text{if } 3 \le k \le5,\\ 6 & \text{if } k \ge6. \end{cases}

Proof. Since r(K3,K3)=6r(K_{3},K_{3}) = 6 [8], Theorem 2.1 implies that

gr⁡23(K3,K3,Kk)=6if k≥6.\operatorname{gr}_{2}^{3}(K_{3},K_{3},K_{k}) = 6 \quad\text{if } k \ge6.

So, assume that 3≤k≤53 \le k \le5. Since r(K3,K3)=6r(K_{3},K_{3}) = 6, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_{3} (and hence, a red/blue K3K_{3}) and a green K3K_{3} (and hence, a red/green K3K_{3}). It follows that gr⁡23(K3,K3,Kk)≥k\operatorname{gr}_{2}^{3}(K_{3},K_{3},K_{k}) \ge k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_{k} that avoids a blue/green KkK_{k} (so, there exists at least one red edge). Since

k≥r(K3,K1)+2=3,k \ge r(K_{3},K_{1}) + 2 = 3,

Lemma 3.1 implies that there exists a red/blue K3K_{3}, a red/green K3K_{3}, or a blue/green KkK_{k}. It follows that gr⁡23(K3,K3,Kk)≤k\operatorname{gr}_{2}^{3}(K_{3},K_{3},K_{k}) \le k. □

Theorem 3.4. If k≥4k \ge4, then

gr⁡23(K3,K4,Kk)={5if k=4,kif 5≤k≤8,9if k≥9.\operatorname{gr}_{2}^{3}(K_{3},K_{4},K_{k}) = \begin{cases} 5 & \text{if } k = 4,\\ k & \text{if } 5 \le k \le8,\\ 9 & \text{if } k \ge9. \end{cases}

Proof. Since r(K3,K4)=9r(K_{3},K_{4}) = 9 [8], Theorem 2.1 implies that

gr⁡23(K3,K4,Kk)=9if k≥9.\operatorname{gr}_{2}^{3}(K_{3},K_{4},K_{k}) = 9 \quad\text{if } k \ge9.

For k<9k < 9, we separate the proof into the following cases.

Case 1: Assume that k=4k = 4. If we let G≅K2G \cong K_{2} (so that ℓ=1\ell= 1 and n=2n = 2) in Lemma 3.2 and note that k≤r(K3,K2)+ℓ=4k \le r(K_{3},K_{2}) + \ell= 4, then it follows that gr⁡23(K3,K4,K4)≥5\operatorname{gr}_{2}^{3}(K_{3},K_{4},K_{4}) \ge5. To prove the reverse inequality, consider a Gallai 3-coloring of K5K_{5} that avoids a blue/green K4K_{4}. Then there exists a red matching of size at least two (otherwise, it is possible to delete a single vertex that removes all red edges, leaving a blue/green K5K_{5}). Since

5≥r(K3,K1)+4=5,5 \ge r(K_{3},K_{1}) + 4 = 5,

Lemma 3.1 implies that there exists a red/blue K3K_{3}, a red/green K4K_{4}, or a blue/green K4K_{4}. It follows that gr⁡23(K3,K4,K4)≤5\operatorname{gr}_{2}^{3}(K_{3},K_{4},K_{4}) \le5.

Case 2: Assume that 5≤k≤85 \le k \le8. Since r(K3,K4)=9r(K_{3},K_{4}) = 9, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_{3} (and hence, a red/blue K3K_{3}) and a green K4K_{4} (and hence, a red/green K4K_{4}). It follows that gr23(K3,K4,Kk)≥kgr^3_2(K_3,K_4,K_k) \ge k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a blue/green KkK_k (so, there exists at least one red edge). Since

k≥r(K3,K2)+2=5,k \ge r(K_3,K_2) + 2 = 5,

Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K4K_4, or a blue/green KkK_k. It follows that gr23(K3,K4,Kk)≤kgr^3_2(K_3,K_4,K_k) \le k. □

Theorem 3.5. If k≥5k \ge5, then

gr23(K3,K5,Kk)={k+1if 5≤k≤7kif 8≤k≤1314if k≥14.gr^3_2(K_3,K_5,K_k) = \begin{cases} k+1 & \text{if } 5 \le k \le7 \\ k & \text{if } 8 \le k \le13 \\ 14 & \text{if } k \ge14. \end{cases}

Proof. Since r(K3,K5)=14r(K_3,K_5) = 14 [8], Theorem 2.1 implies that

gr23(K3,K5,Kk)=14if k≥14.gr^3_2(K_3,K_5,K_k) = 14 \quad\text{if } k \ge14.

For k<14k < 14, we separate the proof into the following cases.

Case 1: Assume that 5≤k≤75 \le k \le7. If we let G≅K2G \cong K_2 (so that ℓ=1\ell= 1 and n=2n = 2) in Lemma 3.2 and note that k≤r(K3,K3)+ℓ=7k \le r(K_3,K_3) + \ell= 7, then it follows that gr23(K3,K5,Kk)≥k+1gr^3_2(K_3,K_5,K_k) \ge k+1. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a blue/green KkK_k. Then there exists a red matching of size at least two (otherwise, it is possible to delete a single vertex that removes all red edges, leaving a blue/green KkK_k). Since k+1≥r(K3,K1)+4=5k+1 \ge r(K_3,K_1) + 4 = 5, Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K5K_5, or a blue/green KkK_k. It follows that gr23(K3,K5,Kk)≤k+1gr^3_2(K_3,K_5,K_k) \le k+1.

Case 2: Assume that 8≤k≤138 \le k \le13. Since r(K3,K5)=14r(K_3,K_5) = 14, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_3 (and hence, a red/blue K3K_3) and a green K5K_5 (and hence, a red/green K5K_5). It follows that gr23(K3,K5,Kk)≥kgr^3_2(K_3,K_5,K_k) \ge k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a blue/green KkK_k (so, there exists at least one red edge). Since

k≥r(K3,K3)+2=8,k \ge r(K_3,K_3) + 2 = 8,

Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K5K_5, or a blue/green KkK_k. It follows that gr23(K3,K5,Kk)≤kgr^3_2(K_3,K_5,K_k) \le k. □

Theorem 3.6. If k≥6k \ge6, then

gr23(K3,K6,Kk)={k+1if 6≤k≤10kif 11≤k≤1718if k≥18.gr^3_2(K_3,K_6,K_k) = \begin{cases} k+1 & \text{if } 6 \le k \le10 \\ k & \text{if } 11 \le k \le17 \\ 18 & \text{if } k \ge18. \end{cases}

Proof. Since r(K3,K6)=18r(K_3,K_6)=18 [16], Theorem 2.1 implies that

gr23(K3,K6,Kk)=18if k≥18.gr_2^3(K_3,K_6,K_k)=18\quad\text{if }k\geq18.

For k<18k<18, we separate the proof into the following cases.

Case 1: Assume that 6≤k≤106\leq k\leq10. If we let G≅K2G\cong K_2 (so that ℓ=1\ell=1 and n=2n=2) in Lemma 3.2 and note that k≤r(K3,K4)+ℓ=10k\leq r(K_3,K_4)+\ell=10, then it follows that gr23(K3,K6,Kk)≥k+1gr_2^3(K_3,K_6,K_k)\geq k+1. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a blue/green KkK_k. Then there exists a red matching of size at least two (otherwise, it is possible to delete a single vertex that removes all red edges, leaving a blue/green KkK_k). Since k+1≥r(K3,K2)+4=7k+1\geq r(K_3,K_2)+4=7, Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K6K_6, or a blue/green KkK_k. It follows that gr23(K3,K6,Kk)≤k+1gr_2^3(K_3,K_6,K_k)\leq k+1.

Case 2: Assume that 11≤k≤1711\leq k\leq17. Since r(K3,K6)=18r(K_3,K_6)=18, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_3 (and hence, a red/blue K3K_3) and a green K6K_6 (and hence, a red/green K6K_6). It follows that gr23(K3,K6,Kk)≥kgr_2^3(K_3,K_6,K_k)\geq k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a blue/green KkK_k (so, there exists at least one red edge). Since

k≥r(K3,K4)+2=11,k\geq r(K_3,K_4)+2=11,

Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K6K_6, or a blue/green KkK_k. It follows that gr23(K3,K6,Kk)≤kgr_2^3(K_3,K_6,K_k)\leq k.

Theorem 3.7

Theorem 3.7. If k≥7k\geq7, then

gr23(K3,K7,Kk)={k+2if 7≤k≤8,k+1if 9≤k≤15,kif 16≤k≤22,23if k≥23.gr_2^3(K_3,K_7,K_k)= \begin{cases} k+2 & \text{if }7\leq k\leq8,\\ k+1 & \text{if }9\leq k\leq15,\\ k & \text{if }16\leq k\leq22,\\ 23 & \text{if }k\geq23. \end{cases}

Proof. Since r(K3,K7)=23r(K_3,K_7)=23 [7, 15], Theorem 2.1 implies that

gr23(K3,K7,Kk)=23if k≥23.gr_2^3(K_3,K_7,K_k)=23\quad\text{if }k\geq23.

For k<23k<23, we separate the proof into the following cases.

Case 1: Assume that 7≤k≤87\leq k\leq8. If we let G≅2K2G\cong2K_2 (so that ℓ=2\ell=2 and n=4n=4) in Lemma 3.2 and note that k≤r(K3,K3)+ℓ=8k\leq r(K_3,K_3)+\ell=8, then it follows that gr23(K3,K7,Kk)≥k+2gr_2^3(K_3,K_7,K_k)\geq k+2. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+2K_{k+2} that avoids a red/blue K3K_3, a red/green K7K_7, and a blue/green KkK_k. Let XX be the set of vertices that are incident with red edges and let YY be the set of vertices that are not in XX. Note that all edges joining vertices in XX to vertices in YY are green, all red edges are contained in the subgraph induced by XX, and all blue edges are contained in the subgraph induced by YY. Since the subgraph induced by X∪{y}X \cup\{y\}, for any y∈Yy \in Y, is a complete red/green subgraph, assume that ∣X∣≤5|X| \leq5. Since the subgraph induced by Y∪{x}Y \cup\{x\}, for any x∈Xx \in X, is a complete blue/green subgraph, assume that ∣Y∣≤k−2|Y| \leq k - 2, which implies that ∣X∣≥k+2−(k−2)=4|X| \geq k + 2 - (k - 2) = 4. The subgraph induced by XX must contain at least one green edge (as a red K3K_3 is avoided), which we denote by x1x2x_1x_2. So, the subgraph induced by Y∪{x1,x2}Y \cup\{x_1, x_2\} is a blue/green complete subgraph, implying that ∣Y∣≤k−3|Y| \leq k - 3. Thus, ∣X∣=5|X| = 5 and ∣Y∣=k−3|Y| = k - 3. From the assumption that k≥7k \geq7, we find that ∣Y∣≥4|Y| \geq4, from which it follows that YY contains a green edge (since a blue K3K_3 is avoided). Denoting such a green edge by y1y2y_1y_2, the subgraph induced by X∪{y1,y2}X \cup\{y_1, y_2\} must be a red/green K7K_7, leading to a contradiction. Hence, every Gallai 3-coloring of Kk+2K_{k+2} contains a red/blue K3K_3, a red/green K7K_7, or a blue/green KkK_k, when 7≤k≤87 \leq k \leq8. It follows that gr23(K3,K7,Kk)≤k+2gr_2^3(K_3, K_7, K_k) \leq k + 2.

Case 2: Assume that 9≤k≤159 \leq k \leq15. If we let G≅K2G \cong K_2 (so that ℓ=1\ell= 1 and n=2n = 2) in Lemma 3.2 and note that k≤r(K3,K5)+ℓ=15k \leq r(K_3, K_5) + \ell= 15, then it follows that gr23(K3,K7,Kk)≥k+1gr_2^3(K_3, K_7, K_k) \geq k + 1. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a blue/green KkK_k. Then there exists a red matching of size at least two (otherwise, it is possible to delete a single vertex that removes all red edges, leaving a blue/green KkK_k). Since k+1≥r(K3,K3)+4=10k + 1 \geq r(K_3, K_3) + 4 = 10, Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K7K_7, or a blue/green KkK_k. It follows that gr23(K3,K7,Kk)≤k+1gr_2^3(K_3, K_7, K_k) \leq k + 1.

Case 3: Assume that 16≤k≤2216 \leq k \leq22. Since r(K3,K7)=23r(K_3, K_7) = 23, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_3 (and hence, a red/blue K3K_3) and a green K7K_7 (and hence, a red/green K7K_7). It follows that gr23(K3,K7,Kk)≥kgr_2^3(K_3, K_7, K_k) \geq k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a blue/green KkK_k (so, there exists at least one red edge). Since

k≥r(K3,K5)+2=16,k \geq r(K_3, K_5) + 2 = 16,

Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K7K_7, or a blue/green KkK_k. It follows that gr23(K3,K7,Kk)≤kgr_2^3(K_3, K_7, K_k) \leq k.

Theorem 3.8. If k≥8k \geq8, then

gr23(K3,K8,Kk)={11if 8≤k≤9,k+2if 10≤k≤11,k+1if 12≤k≤19,kif 20≤k≤27,28if k≥28.gr_2^3(K_3, K_8, K_k) = \begin{cases} 11 & \text{if } 8 \leq k \leq9,\\ k + 2 & \text{if } 10 \leq k \leq11,\\ k + 1 & \text{if } 12 \leq k \leq19,\\ k & \text{if } 20 \leq k \leq27,\\ 28 & \text{if } k \geq28. \end{cases}

Proof. Since r(K3,K8)=28r(K_{3}, K_{8}) = 28 [9, 21], Theorem 2.1 implies that

gr23(K3,K8,Kk)=28if k≥28.gr_{2}^{3}(K_{3}, K_{8}, K_{k}) = 28 \quad\text{if } k \ge28.

For k<28k < 28, we separate the proof into the following cases.

Case 1: Assume that 8≤k≤98 \le k \le9. If we let G≅C5G \cong C_{5} (so that ℓ=2\ell= 2 and n=5n = 5) in Lemma 3.2 and note that 8≤r(K3,K3)+ℓ=88 \le r(K_{3}, K_{3}) + \ell= 8, then it follows that

gr23(K3,K8,K9)≥gr23(K3,K8,K8)≥11.gr_{2}^{3}(K_{3}, K_{8}, K_{9}) \ge gr_{2}^{3}(K_{3}, K_{8}, K_{8}) \ge11.

Next, consider a Gallai 3-coloring of K11K_{11} that avoids a red/blue K3K_{3}, a red/green K8K_{8}, and a blue/green K9K_{9}. Let XX be the set of vertices that are incident with red edges and let YY be the vertices that are not incident with red edges. Note that all edges joining vertices in XX to vertices in YY are green, all red edges are contained in the subgraph induced by XX, and all blue edges are contained in the subgraph induced by YY.

Since the subgraph induced by X∪{y}X \cup\{y\}, for any y∈Yy \in Y, is a complete red/green subgraph, assume that ∣X∣≤6|X| \le6. Since the subgraph induced by Y∪{x}Y \cup\{x\}, for any x∈Xx \in X, is a complete blue/green subgraph, for any x∈Xx \in X, assume that ∣Y∣≤7|Y| \le7. It follows that 4≤∣X∣≤64 \le|X| \le6. If ∣X∣=4|X| = 4 and ∣Y∣=7|Y| = 7, note that XX must contain at least one green edge. The endpoints of such an edge, along with all of the vertices in YY, induce a blue/green K9K_{9}. If ∣X∣=5|X| = 5 and ∣Y∣=6|Y| = 6, then r(K3,K3)=6r(K_{3}, K_{3}) = 6 implies that YY must contain a green K3K_{3}. The vertices in this K3K_{3}, along with all of the vertices in XX, induce a red/green K8K_{8}. If ∣X∣=6|X| = 6 and ∣Y∣=5|Y| = 5, then YY must contain at least one green edge. The endpoints of such an edge, along with all of the vertices in XX, induce a red/green K8K_{8}. It follows that every Gallai 3-coloring of K11K_{11} contains a red/blue K3K_{3}, a red/green K8K_{8}, or a blue/green K9K_{9}. Hence, gr23(K3,K8,K9)≤11gr_{2}^{3}(K_{3}, K_{8}, K_{9}) \le11, from which it follows that

gr23(K3,K8,K8)=gr23(K3,K8,K9)=11.gr_{2}^{3}(K_{3}, K_{8}, K_{8}) = gr_{2}^{3}(K_{3}, K_{8}, K_{9}) = 11.

Case 2: Assume that 10≤k≤1110 \le k \le11. If we let G≅2K2G \cong2K_{2} (so that ℓ=2\ell= 2 and n=4n = 4) in Lemma 3.2 and note that k≤r(K3,K4)+ℓ=11k \le r(K_{3}, K_{4}) + \ell= 11, then it follows that gr23(K3,K8,Kk)≥k+2gr_{2}^{3}(K_{3}, K_{8}, K_{k}) \ge k + 2. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+2K_{k+2} that avoids a red/blue K3K_{3}, a red/green K8K_{8}, and a blue/green KkK_{k}. Let XX be the set of vertices that are incident with red edges, and let YY be the set of vertices that are not incident with red edges.

Since the subgraph induced by Y∪{x}Y \cup\{x\}, for any x∈Xx \in X, is a complete blue/green subgraph, assume that ∣Y∣≤k−2|Y| \le k - 2. It follows that ∣X∣≥4|X| \ge4, so XX must contain at least one green edge, which we denote by x1x2x_1x_2. The subgraph induced by Y∪{x1,x2}Y \cup\{x_1,x_2\} is a blue/green complete subgraph, from which it follows that ∣Y∣≤k−3|Y| \le k-3 and ∣X∣≥5|X| \ge5. Now, ∣Y∣≥k−3≥7|Y| \ge k-3 \ge7 and r(K3,K3)=6r(K_3,K_3)=6 [8] imply that the subgraph induced by YY contains a green K3K_3. This K3K_3, along with five of the vertices in XX, form a red/green K8K_8. It follows that gr23(K3,K8,Kk)≤k+2gr_2^3(K_3,K_8,K_k) \le k+2.

Case 3: Assume that 12≤k≤1912 \le k \le19. If we let G≅K2G \cong K_2 (so that ℓ=1\ell=1 and n=2n=2) in Lemma 3.2 and note that k≤r(K3,K6)+ℓ=19k \le r(K_3,K_6)+\ell=19, then it follows that gr23(K3,K8,Kk)≥k+1gr_2^3(K_3,K_8,K_k) \ge k+1. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a blue/green KkK_k. Then there exists a red matching of size at least two (otherwise, it is possible to delete a single vertex that removes all red edges, leaving a blue/green KkK_k). Since k+1≥r(K3,K4)+4=13k+1 \ge r(K_3,K_4)+4=13, Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K8K_8, or a blue/green KkK_k. It follows that gr23(K3,K8,Kk)≤k+1gr_2^3(K_3,K_8,K_k) \le k+1.

Case 4: Assume that 20≤k≤2720 \le k \le27. Since r(K3,K8)=28r(K_3,K_8)=28, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_3 (and hence, a red/blue K3K_3) and a green K8K_8 (and hence, a red/green K8K_8). It follows that gr23(K3,K8,Kk)≥kgr_2^3(K_3,K_8,K_k) \ge k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a blue/green KkK_k (so, there exists at least one red edge). Since

k≥r(K3,K6)+2=20k \ge r(K_3,K_6)+2=20

Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K8K_8, or a blue/green KkK_k. It follows that gr23(K3,K8,Kk)≤kgr_2^3(K_3,K_8,K_k) \le k. □

Theorem 3.9. If k≥9k \ge9, then

gr23(K3,K9,Kk)={k+3if 9≤k≤11,k+2if 12≤k≤16,k+1if 17≤k≤24,kif 25≤k≤35,36if k≥36.gr_2^3(K_3,K_9,K_k)= \begin{cases} k+3 & \text{if } 9 \le k \le11,\\ k+2 & \text{if } 12 \le k \le16,\\ k+1 & \text{if } 17 \le k \le24,\\ k & \text{if } 25 \le k \le35,\\ 36 & \text{if } k \ge36. \end{cases}

Proof. Since r(K3,K9)=36r(K_3,K_9)=36 [9, 15], Theorem 2.1 implies that

gr23(K3,K9,Kk)=36if k≥36.gr_2^3(K_3,K_9,K_k)=36 \quad\text{if } k \ge36.

For k<36k<36, we separate the proof into the following cases.

Case 1: Suppose that 9≤k≤119 \le k \le11. If we let G≅C5G \cong C_5 (so that ℓ=2\ell=2 and n=5n=5) in Lemma 3.2 and note that k≤r(K3,K4)+ℓ=11k \le r(K_3,K_4)+\ell=11, then it follows that gr23(K3,K9,Kk)≥k+3gr_2^3(K_3,K_9,K_k) \ge k+3. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+3K_{k+3} that avoids a red/blue K3K_3, a red/green K9K_9, and a blue/green KkK_k. Let XX be the set of vertices that are incident with red edges and let YY be the vertices that are not incident with red edges. Note that all edges joining vertices in XX to vertices in YY are green, all red edges are contained in the subgraph induced by XX, and all blue edges are contained in the subgraph induced by YY.

Since the subgraph induced by Y∪{x}Y \cup\{x\}, for any x∈Xx \in X, is a complete blue/green subgraph, assume that ∣Y∣≤k−2|Y| \leq k-2 and ∣X∣≥k+3−(k−2)=5|X| \geq k+3-(k-2)=5. So, XX must contain at least one green edge, which we denote by x1x2x_{1}x_{2}. The subgraph induced by Y∪{x1,x2}Y \cup\{x_{1},x_{2}\} is a blue/green complete subgraph, from which it follows that ∣Y∣≤k−3|Y| \leq k-3 and ∣X∣≥6|X| \geq6. Since the subgraph induced by X∪{y}X \cup\{y\}, for any y∈Yy \in Y, is a red/green complete subgraph, assume that ∣X∣≤7|X| \leq7 and ∣Y∣≥k+3−7=k−4|Y| \geq k+3-7=k-4.

If ∣X∣=6|X|=6 and ∣Y∣=k−3≥6|Y|=k-3 \geq6, then r(K3,K3)=6r(K_{3},K_{3})=6 [8] implies that YY contains a green K3K_{3}. This green K3K_{3}, along with XX, forms a red/green K9K_{9}. If ∣X∣=7|X|=7 and ∣Y∣=k−4≥5|Y|=k-4 \geq5, then YY must contain a green edge, which we denote by y1y2y_{1}y_{2}. The subgraph induced by X∪{y1,y2}X \cup\{y_{1},y_{2}\} is a red/green K9K_{9}. It follows that gr23(K3,K9,Kk)≤k+3gr_{2}^{3}(K_{3},K_{9},K_{k}) \leq k+3.

Case 2: Suppose that 12≤k≤1612 \leq k \leq16. If we let G≅2K2G \cong2K_{2} (so that ℓ=2\ell=2 and n=4n=4) in Lemma 3.2 and note that k≤r(K3,K5)+ℓ=16k \leq r(K_{3},K_{5})+\ell=16, then it follows that gr23(K3,K9,Kk)≥k+2gr_{2}^{3}(K_{3},K_{9},K_{k}) \geq k+2. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+2K_{k+2} that avoids a red/blue K3K_{3}, a red/green K9K_{9}, and a blue/green KkK_{k}. Let XX be the set of vertices that are incident with red edges and let YY be the vertices that are not incident with red edges. Note that all edges joining vertices in XX to vertices in YY are green, all red edges are contained in the subgraph induced by XX, and all blue edges are contained in the subgraph induced by YY.

Since the subgraph induced by Y∪{x}Y \cup\{x\}, for any x∈Xx \in X, is a complete blue/green subgraph, assume that ∣Y∣≤k−2|Y| \leq k-2. It follows that ∣X∣≥4|X| \geq4, so XX must contain at least one green edge, which we denote by x1x2x_{1}x_{2}. The subgraph induced by Y∪{x1,x2}Y \cup\{x_{1},x_{2}\} is a blue/green complete subgraph, from which it follows that ∣Y∣≤k−3|Y| \leq k-3 and ∣X∣≥5|X| \geq5. Since the subgraph induced by X∪{y}X \cup\{y\}, for any y∈Yy \in Y, is a red/green complete subgraph, assume that ∣X∣≤7|X| \leq7 and ∣Y∣≥k+2−7=k−5|Y| \geq k+2-7=k-5.

If ∣X∣=5|X|=5 and ∣Y∣=k+2−5=k−5≥9|Y|=k+2-5=k-5 \geq9, then r(K3,K4)=9r(K_{3},K_{4})=9 [8] implies that the subgraph induced by YY contains a green K4K_{4}. The vertices in this green K4K_{4}, along with XX, form a red/green K9K_{9}. If 6≤∣X∣≤76 \leq|X| \leq7 and k−5≤∣Y∣≤k−4k-5 \leq|Y| \leq k-4, then ∣Y∣≥7|Y| \geq7 and r(K3,K3)=6r(K_{3},K_{3})=6 [8] implies that there exists a green K3K_{3} in YY. The vertices of this K3K_{3}, along with XX, form a red/green K9K_{9}. It follows that gr23(K3,K9,Kk)≤k+2gr_{2}^{3}(K_{3},K_{9},K_{k}) \leq k+2.

Case 3: Suppose that 17≤k≤2417 \leq k \leq24. If we let G≅K2G \cong K_{2} (so that ℓ=1\ell=1 and n=2n=2) in Lemma 3.2 and note that k≤r(K3,K7)+ℓ=24k \leq r(K_{3},K_{7})+\ell=24, then it follows that gr23(K3,K9,Kk)≥k+1gr_{2}^{3}(K_{3},K_{9},K_{k}) \geq k+1. To prove the reverse inequality, consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a blue/green KkK_k. Then there exists a red matching of size at least two (otherwise, it is possible to delete a single vertex that removes all red edges, leaving a blue/green KkK_k). Since k+1≥r(K3,K5)+4=18k+1 \ge r(K_3,K_5)+4=18, Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K9K_9, or a blue/green KkK_k. It follows that gr23(K3,K9,Kk)≤k+1gr^3_2(K_3,K_9,K_k) \le k+1.

Case 4: Suppose that 25≤k≤3525 \le k \le35. Since r(K3,K9)=36r(K_3,K_9)=36, there exists a blue/green Kk−1K_{k-1} that avoids a blue K3K_3 (and hence, a red/blue K3K_3) and a green K9K_9 (and hence, a red/green K9K_9). It follows that gr23(K3,K9,Kk)≥kgr^3_2(K_3,K_9,K_k) \ge k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a blue/green KkK_k (so, there exists at least one red edge). Since

k≥r(K3,K7)+2=25,k \ge r(K_3,K_7)+2=25,

Lemma 3.1 implies that there exists a red/blue K3K_3, a red/green K9K_9, or a blue/green KkK_k. It follows that gr23(K3,K9,Kk)≤kgr^3_2(K_3,K_9,K_k) \le k.

Note that in many of the proofs in this section, Theorem 2.2 could have been used to prove the upper bounds across ranges of kk once the first value in the range was determined. Since our upper bound proofs worked across each range for kk, this approach was not necessary. In the next section, Theorem 2.2 will play a more significant role in the proofs of upper bounds.

The Chromatic Gallai-Ramsey Number gr23(K4,Kj,Kk)gr^3_2(K_4,K_j,K_k)

The value r(K4,K4,K4)=10r(K_4,K_4,K_4)=10 was determined in [4]. The following theorem provides a generalization of the Gallai analogue of this result.

Theorem 4.1. If k≥4k \ge4, then

gr23(K4,K4,Kk)={k+1if 4≤k≤8,kif 9≤k≤17,18if k≥18.gr^3_2(K_4,K_4,K_k)= \begin{cases} k+1 & \text{if }4 \le k \le8,\\ k & \text{if }9 \le k \le17,\\ 18 & \text{if }k \ge18. \end{cases}

Proof. Since r(K4,K4)=18r(K_4,K_4)=18 [8], Theorem 2.1 implies that

gr23(K4,K4,Kk)=18if k≥18.gr^3_2(K_4,K_4,K_k)=18 \quad\text{if } k \ge18.

For k<18k<18, we separate the proof into the following cases.

Case 1: Suppose that k=4k=4. The Gallai 3-coloring of K4K_4 shown in Figure 1a avoids a red/blue K4K_4, a red/green K4K_4, and a blue/green K4K_4. It follows that gr23(K4,K4,K4)≥5gr^3_2(K_4,K_4,K_4) \ge5. To prove the reverse inequality, consider a Gallai 3-coloring of K5K_5 and let B\mathcal{B} be the base graph, chosen to have minimal order. If a K4K_4-subgraph whose edges use at most two colors is avoided, then Theorem 1.1 and Lemma 1.2 imply that ∣V(B)∣=2|V(\mathcal{B})|=2. Suppose that the edges joining the two blocks are red. We must consider two subcases.

Figure 1. Critical colorings for gr23(K4,K4,Kk)gr^{3}_{2}(K_{4},K_{4},K_{k}), when 4≤k≤84 \le k \le8.

Subcase 1.1: Assume that one block contains a single vertex, which we denote by xx, and the other block has order 4, with vertex set YY. Then Lemma 1.4 implies that the subgraph induced by YY does not contain any red edges (as such an edge, along with xx, would form a red K3K_{3}, resulting in a red/blue K4K_{4} or a red/green K4K_{4}). So, the subgraph induced by YY forms a blue/green K4K_{4}.

Subcase 1.2: Assume that one block has order 2 and the other block has order 3. Denote the vertex sets for the blocks by X={x1,x2}X=\{x_{1},x_{2}\} and Y={y1,y2,y3}Y=\{y_{1},y_{2},y_{3}\}. Once again, we note that the subgraphs induced by XX and YY cannot contain any red edges. Without loss of generality, suppose that x1x2x_{1}x_{2} is blue. If any edge in YY is blue (say, y1y2y_{1}y_{2} is blue), then the subgraph induced by {x1,x2,y1,y2}\{x_{1},x_{2},y_{1},y_{2}\} is a red/blue K4K_{4}. So, all of the edges in YY must be green, and the subgraph induced by {x1,y1,y2,y3}\{x_{1},y_{1},y_{2},y_{3}\} is a red/green K4K_{4}. In all cases, there exists a K4K_{4}-subgraph whose edges use at most two colors. It follows that gr23(K4,K4,K4)=5gr^{3}_{2}(K_{4},K_{4},K_{4})=5.

Case 2: Suppose that 5≤k≤85 \le k \le8. The Gallai 3-colorings of KkK_{k} shown in Figure 1b, Figure 1c, Figure 1d, and Figure 1e provide the lower bounds gr23(K4,K4,Kk)≥k+1gr^{3}_{2}(K_{4},K_{4},K_{k}) \ge k+1 for k=5,6,7,k=5,6,7, and 88, respectively. The reverse inequality follows from induction on 4≤k≤84 \le k \le8, with the base case corresponding to Case 1 of this proof. Suppose that gr23(K4,K4,Kk−1)≤kgr^{3}_{2}(K_{4},K_{4},K_{k-1}) \le k and consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a red/blue K4K_{4} and a red/green K4K_{4}. By Theorem 2.2, every vertex is incident with a red edge, or there exists a red/blue K4K_4, a red/green K4K_4, or a blue/green KkK_k. Assume the former case and also note that by the inductive hypothesis, there exists a blue/green Kk−1K_{k-1}, whose vertex set we denote by X:={x1,x2,…,xk−1}X := \{x_1, x_2, \ldots, x_{k-1}\}. Denote the other two vertices by yy and zz.

By the inductive hypothesis, the subgraph induced by {x2,…,xk−1,y,z}\{x_2, \ldots, x_{k-1}, y, z\} must contain a blue/green Kk−1K_{k-1}, which must necessarily include one of yy or zz. Without loss of generality, suppose that {x2,…,xk−1,y}\{x_2, \ldots, x_{k-1}, y\} induces a blue/green Kk−1K_{k-1}. If the subgraph induced by {x1,x2,…,xk−1,y}\{x_1, x_2, \ldots, x_{k-1}, y\} is not a blue/green KkK_k, then x1yx_1y must be red and yy joins to {x1,x2,…,xk−1}\{x_1, x_2, \ldots, x_{k-1}\} with only blue and green edges. It follows that x2z,…,xk−1zx_2z, \ldots, x_{k-1}z are all red edges. Without loss of generality suppose that yzyz is red or blue. If yzyz is red, then depending on the color of x1x2x_1x_2 (which is blue or green), the subgraph induced by {x1,x2,y,z}\{x_1, x_2, y, z\} is a red/blue or red/green K4K_4. So, suppose that yzyz is blue. If x1x2x_1x_2 is also blue, then the subgraph induced by {x1,x2,y,z}\{x_1, x_2, y, z\} is a red/blue K4K_4. So, assume that x1x2x_1x_2 is green. Then x1yx_1y must be red, contradicting the fact that {x2,…,xk−1,y}\{x_2, \ldots, x_{k-1}, y\} induces a blue/green Kk−1K_{k-1}. It follows that gr23(K4,K4,Kk)≤k+1gr_2^3(K_4, K_4, K_k) \le k + 1.

Case 3: Suppose that k=9k = 9. Since r(K4,K4)=18r(K_4, K_4) = 18 [8], there exists a blue/green K8K_8 that avoids a blue K4K_4 (and hence, a red/blue K4K_4) and a green K4K_4 (and hence, a red/green K4K_4). As there are not enough vertices to form a blue/green K9K_9, it follows that gr23(K4,K4,K9)≥9gr_2^3(K_4, K_4, K_9) \ge9. To prove the reverse inequality, consider a Gallai 3-coloring of K9K_9 that avoids a red/blue K4K_4, a red/green K4K_4, and a blue/green K9K_9. Let B\mathcal{B} be the base graph, chosen to have minimal order. Theorem 1.1 and Lemma 1.2 imply that 2≤∣V(B)∣≤82 \le|V(\mathcal{B})| \le8 and ∣V(B)∣≠3|V(\mathcal{B})| \ne3. Consider the following subcases.

Subcase 3.1: Suppose that ∣V(B)∣=2|V(\mathcal{B})| = 2. If the edge in B\mathcal{B} is red, then assume that neither block contains a red edge, as this would result in a red K3K_3, and hence, a red/blue K4K_4 or a red/green K4K_4 by Lemma 1.4. There are two subsubcases to consider.

Subsubcase 3.1.1: Suppose that one block in B\mathcal{B} contains only one vertex, which we denote by xx. Let YY be the vertex set for the other block. If the edge in B\mathcal{B} is red, then r(K3,K3)=6r(K_3, K_3) = 6 [8] implies that the subgraph induced by YY contains a red/blue K3K_3 or a green K3K_3. Such a subgraph, along with xx, forms a red/blue K4K_4 or a red/green K4K_4, respectively. So, assume that the edge in B\mathcal{B} is blue or green (without loss of generality, suppose it is blue). By Theorem 3.4, gr23(K3,K4,K8)=8gr_2^3(K_3, K_4, K_8) = 8, from which it follows that the subgraph induced by YY contains a red/blue K3K_3, a red/green K4K_4, or a blue/green K8K_8. In the first case, including xx results in a red/green K4K_4, and in the last case, including xx results in a blue/green K9K_9.

Subsubcase 3.1.2: Suppose that both blocks have order at least 2. If the edge in B\mathcal{B} is red, then no red edge exists in either block as such an edge would result in a red K3K_{3}, and by Lemma 1.4, there would exist a red/blue K4K_{4} or a red/green K4K_{4}. If both blocks contain a blue edge or if both blocks contain a green edge, then such a pair of edges results in a red/blue K4K_{4} or a red/green K4K_{4}, respectively. Hence, one block must form a red/blue complete graph and the other must form a red/green complete graph. By the pigeonhole principle, one block contains at least five vertices forming a blue K5K_{5} or a green K5K_{5}.

If the edge in B\mathcal{B} is blue or green (assume it is blue), then at most one of the blocks can contain a red or a blue edge; otherwise, a red/blue K4K_{4} can be formed. Hence, one block is a complete green graph, which has order 2 or 3. If its order is 2, then the other block has order 7, and by Theorem 3.4, gr23(K3,K4,K7)=7gr_{2}^{3}(K_{3}, K_{4}, K_{7}) = 7. So, it contains a red/blue K3K_{3}, a red/green K4K_{4}, or a blue/green K7K_{7}. In the first case, including one vertex from the smaller block results in a red/blue K4K_{4}. In the last case, including both of the vertices from the smaller block results in a blue/green K9K_{9}. If the complete green block has order 3, then the other block has order 6, and by Theorem 3.4, gr23(K3,K4,K6)=6gr_{2}^{3}(K_{3}, K_{4}, K_{6}) = 6. So, it contains a red/blue K3K_{3}, a red/green K4K_{4}, or a blue/green K6K_{6}. In the first case, including one vertex from the smaller block results in a red/blue K4K_{4}. In the last case, including all three of the vertices from the smaller block results in a blue/green K9K_{9}.

Subcase 3.2: Suppose that 4≤∣V(B)∣≤84 \le\lvert V(\mathcal{B}) \rvert\le8. If the edges in B\mathcal{B} are red/blue or red/green, then a red/blue K4K_{4} or a red/green K4K_{4} exists. So, assume that B\mathcal{B} is a blue/green complete graph. Also, note that every vertex in B\mathcal{B} is incident with both a blue edge and a green edge; otherwise, the Gallai coloring can be formed with a base graph of order 2. Some block must contain a red edge, or the Gallai coloring is a blue/green KkK_{k}. Also, at most one block contains a red edge; otherwise, a red/blue K4K_{4} or a red/green K4K_{4} can be formed. Let xyxy be the unique red edge and denote the other seven vertices by z1,z2,…,z7z_{1}, z_{2}, \ldots, z_{7}. Since rainbow triangles are avoided, xzixz_{i} and yziyz_{i} are both blue or both green, for each i∈{1,2,…,7}i \in\{1, 2, \ldots, 7\}. By the pigeonhole principle, at least four of the vertices in {z1,z2,…,z7}\{z_{1}, z_{2}, \ldots, z_{7}\} join to xx and yy with the same color. Without loss of generality, suppose that xz1xz_{1}, yz1yz_{1}, xz2xz_{2}, yz2yz_{2}, xz3xz_{3}, yz3yz_{3}, xz4xz_{4}, and yz4yz_{4} are all blue. If any edge in the subgraph induced by {z1,z2,z3,z4}\{z_{1}, z_{2}, z_{3}, z_{4}\} is blue, then that edge, along with xx and yy, forms a red/blue K4K_{4}. Thus, {z1,z2,z3,z4}\{z_{1}, z_{2}, z_{3}, z_{4}\} induces a green K4K_{4}.

In both subcases, we find that there exists a red/blue K4K_{4}, a red/green K4K_{4}, or a blue/green K9K_{9}. It follows that gr23(K4,K4,K9)≤9gr_{2}^{3}(K_{4}, K_{4}, K_{9}) \le9.

Case 4: Suppose that 10≤k≤1710 \le k \le17. Since r(K4,K4)=18r(K_4,K_4)=18 [8], there exists a blue/green Kk−1K_{k-1} that avoids a blue K4K_4 (and hence, a red/blue K4K_4) and a green K4K_4 (and hence, a red/green K4K_4). As there are not enough vertices to form a blue/green KkK_k, it follows that gr23(K4,K4,Kk)≥kgr^3_2(K_4,K_4,K_k) \ge k. The reverse inequality follows from induction on 9≤k≤179 \le k \le17, with the base case corresponding to Case 3 of this proof. Suppose that gr23(K4,K4,Kk−1)≤k−1gr^3_2(K_4,K_4,K_{k-1}) \le k-1 and consider a Gallai 3-coloring of KkK_k that avoids a red/blue K4K_4 and a red/green K4K_4. By Theorem 2.2, every vertex is incident with a red edge, or there exists a red/blue K4K_4, a red/green K4K_4, or a blue/green KkK_k. Assume the former case and also note that by the inductive hypothesis, there exists a blue/green Kk−1K_{k-1}, whose vertex set we denote by X:={x1,x2,…,xk−1}X:=\{x_1,x_2,\ldots,x_{k-1}\}. Denote the other vertex by yy. The only way for every vertex to be incident with a red edge is if yxiyx_i is red for all i∈{1,2,…,k−1}i \in\{1,2,\ldots,k-1\}. The subgraph induced by {x1,x2,…,xk−1}\{x_1,x_2,\ldots,x_{k-1}\} is a blue/green complete graph of order k−1≥9k-1 \ge9, so it must contain a blue K3K_3 or a green K3K_3 since r(K3,K3)=6r(K_3,K_3)=6 [8]. Such a K3K_3-subgraph, along with yy, forms a red/blue K4K_4 or a red/green K4K_4, respectively. It follows that gr23(K4,K4,Kk)≤kgr^3_2(K_4,K_4,K_k) \le k. □

Theorem 4.2. If k≥5k \ge5, then

gr23(K4,K5,Kk)={k+2if 5≤k≤9k+1if 10≤k≤14kif 15≤k≤2425if k≥25.gr^3_2(K_4,K_5,K_k)= \begin{cases} k+2 & \text{if } 5 \le k \le9\\ k+1 & \text{if } 10 \le k \le14\\ k & \text{if } 15 \le k \le24\\ 25 & \text{if } k \ge25. \end{cases}

Proof. Since r(K4,K5)=25r(K_4,K_5)=25 [14, 20], Theorem 2.1 implies that

gr23(K4,K5,Kk)=25if k≥25.gr^3_2(K_4,K_5,K_k)=25 \quad\text{if } k \ge25.

For k<25k<25, we separate the proof into the following cases. Case 1: Suppose that k=5k=5. The Gallai 3-coloring of K6K_6 shown in Figure 2a avoids a red/blue K4K_4, a red/green K5K_5, and a blue/green K5K_5. It follows that gr23(K4,K5,K5)≥7gr^3_2(K_4,K_5,K_5) \ge7. To prove the reverse inequality, consider a Gallai 3-coloring of K7K_7, and let B\mathcal{B} be the base graph, chosen to have minimal order. By Theorem 1.1 and Lemma 1.2, ∣V(B)∣∈{2,4}|V(\mathcal{B})| \in\{2,4\}.

Figure 2. Critical colorings for gr23(K4,K5,Kk)gr_2^3(K_4,K_5,K_k), when 5≤k≤95 \le k \le9.

Subcase 1.1: Suppose that ∣V(B)∣=2|V(\mathcal{B})|=2. First, consider the possibility that the edge in B\mathcal{B} is red or blue (without loss of generality, suppose that it is red). By Theorem 3.4, gr23(K3,K4,K5)=5gr^3_2(K_3,K_4,K_5)=5. So, if a block has order at least 5, then it contains a red/blue K3K_3, a red/green K4K_4, or a blue/green K5K_5. In the first case, including a single vertex from the smaller block results in a red/blue K4K_4. In the second case, including a single vertex from the smaller block results in a red/green K5K_5. Thus, assume that one block has order 4 and the other block has order 3, and we denote their vertex sets by XX and YY, respectively. If the subgraph induced by YY is a red/blue K3K_3, then including a vertex from XX results in a red/blue K4K_4. If the subgraph induced by YY is a red/green K3K_3, then if any red or blue edge exists in the subgraph induced by XX, that edge, along with the vertices in YY, forms a red/green K5K_5. So, assume that the subgraph induced by YY is a blue/green K3K_3. If the subgraph induced by YY contains a blue edge, then the subgraph induced by XX cannot contain a red or blue edge without forming a red/blue K4K_4. So, assume that the subgraph induced by YY is a green K3K_3. If the subgraph induced by XX contains a red or green edge, then such an edge, along with YY, forms a red/green K5K_5. So, assume that all of the edges in the subgraph induced by XX are blue, forming a blue K4K_4.

Now consider the case where the edge in BB is green. By Theorem 4.1, gr23(K4,K4,K4)=5gr_2^3(K_4,K_4,K_4)=5. So, if a block has order at least 5, then it contains a K4K_4 whose edges use at most two colors. If such a K4K_4 is red/green or blue/green, then including a single vertex from the other block results in a red/green K5K_5 or a blue/green K5K_5, respectively. The only other possibility is that it contains a red/blue K4K_4. Thus, assume that one block has order 4 and the other block has order 3, and we denote their vertex sets by XX and YY, respectively. If XX contains a red/green K3K_3, then YY cannot contain a red or green edge without resulting in a red/green K5K_5. So, suppose that YY induces a blue K3K_3. Then if XX contains a blue or green edge, that edge, along with YY, forms a blue/green K5K_5. So, XX must induce a red K4K_4. If XX contains a blue/green K3K_3, then YY cannot contain a blue or green edge without resulting in a blue/green K5K_5. So, suppose that YY induces a red K3K_3. Then if XX contains a red or green edge, that edge, along with YY, forms a red/green K5K_5. So, XX must induce a blue K4K_4. Finally, consider the case where XX does not contain a red/green K3K_3 or a blue/green K3K_3. Then the subgraph induced by XX must be a red/blue K4K_4.

Subcase 1.2: Suppose that ∣V(B)∣=4|V(\mathcal{B})| = 4. If the edges in B\mathcal{B} are red and blue, then a red/blue K4K_4 can be formed by selecting a single vertex from each block. So, assume that the edges in B\mathcal{B} are red/green or blue/green (without loss of generality, assume that they are red/green). If any block contains a red or green edge, then that edge, along with a single vertex from each of the other blocks, forms a red/green K5K_5. So the edges in all of the blocks must be blue. Note that every vertex in B\mathcal{B} is incident with both red and green edges, otherwise, the Gallai 3-coloring corresponds with a base graph of order 2, contradicting the minimality of the order of B\mathcal{B}. If any block has order at least three, then selecting a single vertex from a block that is red-adjacent to the block of order at least 3 results in a red/blue K4K_4. So, three blocks have order 2 and one block has order 1. Avoiding a red/blue K4K_4 also forces the blocks of order 2 to all be green-adjacent, forming a blue/green K6K_6.

In both subcases, we find that there exists a red/blue K4K_4, a red/green K5K_5, or a blue/green K5K_5. It follows that gr⁡23(K4,K5,K5)≤7\operatorname{gr}_2^3(K_4,K_5,K_5) \le7.

Case 2: Suppose that 6≤k≤96 \le k \le9. The Gallai 3-colorings of Kk+1K_{k+1} given in Figure 2b, Figure 2c, Figure 2d, and Figure 2e imply the lower bound

gr⁡23(K4,K5,Kk)≥k+2\operatorname{gr}_2^3(K_4,K_5,K_k) \ge k+2

when k=6k = 6, 7, 8, and 9, respectively. In each case, the colorings avoid a red/blue K4K_4, a red/green K5K_5, and a blue/green KkK_k.

To prove the reverse inequality, we use induction on 5≤k≤95 \le k \le9, with Case 1 of this proof serving as the base case. For 6≤k≤96 \le k \le9, assume that gr⁡23(K4,K5,Kk−1)≤k+1\operatorname{gr}_2^3(K_4,K_5,K_{k-1}) \le k+1, and consider a Gallai 3-coloring of Kk+2K_{k+2} that avoids a red/blue K4K_4 and a red/green K5K_5. By the inductive hypothesis, there exists a blue/green Kk−1K_{k-1}. Also, by Theorem 2.2, every vertex must be incident with a red edge. Let B\mathcal{B} be the base graph for this Gallai 3-coloring of Kk+2K_{k+2}, chosen to have minimal order. By Theorem 1.1 and Lemma 1.2, if a blue/green KkK_k is avoided, then ∣V(B)∣∈{2,4,5,…,k−1}|V(\mathcal{B})| \in\{2,4,5,\ldots,k-1\}.

Subcase 2.1: Suppose that ∣V(B)∣=2|V(\mathcal{B})| = 2. First, consider the possibility that the edge in B\mathcal{B} is red. Then it is not possible for both blocks to be contain a red or blue edge as two such edges would produce a red/blue K4K_4. Denote the vertex sets for the blocks by XX and YY, and assume that YY does not contain any red or blue edges. If ∣Y∣≥4|Y| \ge4, then selecting x∈Xx \in X, the subgraph induced by {x}∪Y\{x\} \cup Y is a red/green K5K_5. So, assume that ∣Y∣≤3|Y| \le3. If ∣Y∣=3|Y| = 3, then if XX contains a red or green edge, that edge, along with YY, forms a red/green K5K_5. If XX does not contain any red or green edges, then the subgraph induced by XX is a blue Kk−1K_{k-1}, with k−1≥5k-1 \ge5. If ∣Y∣=2|Y| = 2, then ∣X∣=k≥6|X| = k \ge6. Since r(K3,K3)=6r(K_3,K_3) = 6 [8], the subgraph induced by XX contains a red/green K3K_3 or a blue K3K_3. In the former case, the red/green K3K_3, along with the vertices in YY, forms a red/green K4K_4. In the latter case, the blue K3K_3, along with any vertex from YY, forms a red/blue K4K_4. If ∣Y∣=1|Y| = 1, then ∣X∣=k+1≥7|X| = k+1 \ge7. By Theorem 4.1, gr⁡23(K4,K4,Kk)≤k+1\operatorname{gr}_2^3(K_4,K_4,K_k) \le k+1, for all 6≤k≤96 \le k \le9, so the subgraph induced by XX contains a red/blue K4K_4, a red/green K4K_4, or a blue/green KkK_k. In the second case, a red/green K4K_4, along with a vertex from YY, results in a red/green K5K_5.

Next, suppose that the edge in B\mathcal{B} is blue. In order for every vertex to be incident with a red edge, each block must contain a red edge. The vertices for two such edges induce a red/blue K4K_4.

Finally, suppose that the edge in B\mathcal{B} is green. By the pigeonhole principle, one block must contain at least ⌈k+22⌉≥4\left\lceil\frac{k+2}{2} \right\rceil\ge4 vertices. Without loss of generality, suppose that the vertex sets for the blocks are denoted by XX and YY, and ∣X∣≥4|X| \ge4. In order for every vertex to be incident with a red edge, each block must contain a red edge, so it follows that ∣Y∣≥2|Y| \ge2. If XX contains a red/green K3K_3, then that K3K_3, along with a red edge from YY, forms a red/green K5K_5. So, assume that XX does not contain any red/green K3K_3-subgraphs. If XX contains two disjoint red edges, then those edges must be joined by blue edges, forming a red/blue K4K_4. If no two disjoint red edges exist in XX, then in order for every vertex to be incident with a red edge, XX must contain a red K1,3K_{1,3}. The leaves of such a K1,3K_{1,3} can only be joined by blue edges, resulting in a red/blue K4K_4.

Subcase 2.2: Suppose that ∣V(B)∣=4|V(\mathcal{B})| = 4. If the edges in B\mathcal{B} are red and blue, then a red/blue K4K_4 can be formed by selecting a single vertex from each block. If the edges in B\mathcal{B} are red and green, then no red or green edge exists in any of the blocks without producing a red/green K5K_5. So, assume that all blocks form complete blue subgraphs. By the minimality of B\mathcal{B}, all vertices in B\mathcal{B} are incident with both red and green edges. So, if any block contains three or more vertices, then that block, along with a single vertex from another red-adjacent block, forms a red/blue K4K_4. Hence, we assume that each block has order at most 2, from which it follows that k+2≤8k+2 \le8 (i.e., k=6k=6). As each block must then have order exactly two, the vertices in two red-adjacent blocks will form a red/blue K4K_4.

Assume that the edges in B\mathcal{B} are blue and green. Since B\mathcal{B} is chosen to have minimal order, it follows that every vertex in B\mathcal{B} is incident with both blue and green edges. By Theorem 2.2, every vertex must be incident with a red edge. So, each block has order at least two and contains a red edge. Selecting two red edges from distinct blocks that are joined by blue edges results in a red/blue K4K_4.

Subcase 2.3: Suppose that ∣V(B)∣∈{5,6,7,8}|V(\mathcal{B})| \in\{5,6,7,8\}. Then the edges in B\mathcal{B} are blue and green. Since B\mathcal{B} is chosen to have minimal order, it follows that every vertex in B\mathcal{B} is incident with both blue and green edges. If a block only contains a single vertex, then that vertex is not incident with any red edges, contradicting Theorem 2.2. So, each block has order at least two and contains a red edge. Selecting two red edges from distinct blocks that are joined by blue edges results in a red/blue K4K_4.

Case 3: Suppose that k=10k=10. While the Gallai 3-coloring of K10K_{10} given in Figure 2e provides the lower bound gr23(K4,K5,K10)≥11gr^3_2(K_4,K_5,K_{10}) \ge11, it is not unique. The Gallai 3-coloring of K10K_{10} shown in Figure 3 avoids a red/blue K4K_4, a red/green K5K_5, and a blue/green K10K_{10} (here, the block consisting of blue and green edges is a critical coloring for r(K4,K3)r(K_4,K_3) in colors blue and green), and it sets us up for the lower bound construction we will use in the next case.

Figure 3. A critical coloring for gr23(K4,K5,K10)gr^3_2(K_4,K_5,K_{10}).

To prove that gr23(K4,K5,K10)≤11gr^3_2(K_4,K_5,K_{10}) \le11, consider a Gallai 3-coloring of K11K_{11} that avoids a red/blue K4K_4, a red/green K5K_5, and a blue/green K10K_{10}. A red edge must exist, otherwise, it is a blue/green K11K_{11}. Let xx be a vertex that is incident with a red edge. Denote by Nr(x)N_r(x), Nb(x)N_b(x), and Ng(x)N_g(x) the red, blue, and green neighborhoods of xx, respectively. It is possible that Nb(x)N_b(x) or Ng(x)N_g(x) could be empty, but ∣Nr(x)∣≥1|N_r(x)| \ge1 by assumption. Since rainbow triangles are avoided, all edges joining Nr(x)N_r(x) and Nb(x)N_b(x) are red or blue. If either of Nr(x)N_r(x) or Nb(x)N_b(x) contain a red or blue edge, then that edge, along with xx and a single vertex from the other set, forms a red/blue K4K_4. So, if Nr(x)N_r(x) contains any edges, they must be green (the same is true for Nb(x)N_b(x)). Also, avoiding a rainbow triangle forces all edges joining Nr(x)N_r(x) and Ng(x)N_g(x) to be red or green. Consider two subcases.

Subcase 3.1: Suppose that ∣Nr(x)∣=1|N_r(x)| = 1 and let yy be the vertex in Nr(x)N_r(x). Since the subgraph induced by Nb(x)N_b(x) only contains green edges, and a green K5K_5 is avoided, it follows that ∣Nb(x)∣≤4|N_b(x)| \le4 and ∣Ng(x)∣≥5|N_g(x)| \ge5. Note that a red edge must exist in the subgraph induced by Ng(x)N_g(x) (otherwise, the deletion of yy would result in a blue/green K10K_{10}). Let z1z2z_1z_2 be a red edge such that z1,z2∈Ng(x)z_1,z_2 \in N_g(x) and let z3,z4,z5∈Ng(x)z_3,z_4,z_5 \in N_g(x) be three other vertices. If zizjz_i z_j is green for any i∈{1,2}i \in\{1,2\} and j∈{3,4,5}j \in\{3,4,5\}, then the subgraph induced by {z1,z2,zj}\{z_1,z_2,z_j\} is a red/green K3K_3 that, along with xx and yy, forms a red/green K5K_5. So, all edges of the form zizjz_i z_j are red or blue. If any edge in the subgraph induced by {z3,z4,z5}\{z_3,z_4,z_5\} is red or blue, then that edge, along with z1z_1 and z2z_2, forms a red/blue K4K_4. Hence, the subgraph induced by {z3,z4,z5}\{z_3,z_4,z_5\} is a green K3K_3 that, along with xx and yy, forms a red/green K5K_5.

Subcase 3.2: Suppose that ∣Nr(x)∣≥2|N_r(x)| \ge2. If the subgraph induced by Ng(x)N_g(x) contains a red or green edge, then that edge, along with xx and a green edge in Nr(x)N_r(x), forms a red/green K5K_5. So, Ng(x)N_g(x) only contains blue edges and ∣Ng(x)∣≤3|N_g(x)| \le3 in order to avoid a blue K4K_4. Since Nr(x)N_r(x) only contains green edges, if ∣Nr(x)∣≥3|N_r(x)| \ge3, then selecting three vertices from Nr(x)N_r(x), one vertex from Ng(x)N_g(x), and vertex xx, results in a red/green K5K_5. It follows that ∣Nr(x)∣≤2|N_r(x)| \le2, which implies that ∣Nb(x)∣≥5|N_b(x)| \ge5. Since Nb(x)N_b(x) only contains green edges, it contains a green K5K_5.

In both subcases, we find that there exists a red/blue K4K_4, a red/green K5K_5, or a blue/green K10K_{10}. It follows that gr32(K4,K5,K10)≤11gr_3^2(K_4,K_5,K_{10}) \le11.

Case 4: Suppose that 11≤k≤1411 \le k \le14. For the lower bound, we start with the construction given in Figure 3, and add in a green Kk−10K_{k-10}, as shown in Figure 4. Here, the subgraph induced by {x1,x2,…,x8}\{x_1,x_2,\ldots,x_8\} is a critical coloring for r(K4,K3)r(K_4,K_3) (in colors blue and green). Suppose that the vertex set for the green Kk−10K_{k-10}-subgraph is given by {y1,y2,…,yk−10}\{y_1,y_2,\ldots,y_{k-10}\}, and the edges xiyjx_i y_j are colored blue if ii and jj have the same parity and green if they have different parities. The resulting Gallai 3-coloring of KkK_k avoids a red/blue K4K_4, a red/green K5K_5, and a blue/green KkK_k. It follows that gr23(K4,K5,Kk)≥k+1gr_2^3(K_4,K_5,K_k) \ge k+1.

Figure 4. Constructing a critical coloring for gr23(K4,K5,Kk)gr^{3}_{2}(K_4,K_5,K_k), when 11≤k≤1411 \le k \le14.

To prove the reverse inequality, we use induction on 10≤k≤1410 \le k \le14, with Case 3 of this proof serving as the base case. For $11 \le k \le 14, assume that gr23(K4,K5,Kk−1)≤kgr^{3}_{2}(K_4,K_5,K_{k-1}) \le k and consider a Gallai 3-coloring of Kk+1K_{k+1} that avoids a red/blue K4K_4 and a red/green K5K_5. By the inductive hypothesis, there exists a blue/green Kk−1K_{k-1}. Note that 10≤k−1≤1310 \le k-1 \le13, from which r(K3,K4)=9r(K_3,K_4)=9 implies that the blue/green Kk−1K_{k-1} contains a blue K3K_3 or a green K4K_4. By Theorem 2.2, every vertex must be incident with at least one red edge. If {x1,x2,x3}\{x_1,x_2,x_3\} induces a blue K3K_3 and yx1yx_1 is red, then the subgraph induced by {x1,x2,x3,y}\{x_1,x_2,x_3,y\} is a red/blue K4K_4. If {x1,x2,x3,x4}\{x_1,x_2,x_3,x_4\} induces a green K4K_4 and yx1yx_1 is red, then the subgraph induced by {x1,x2,x3,x4,y}\{x_1,x_2,x_3,x_4,y\} is a red/green K5K_5. It follows that gr23(K4,K5,Kk)≤k+1gr^{3}_{2}(K_4,K_5,K_k) \le k+1.

Case 5: Suppose that 15≤k≤2415 \le k \le24. Since r(K4,K5)=25r(K_4,K_5)=25 [8], there exists a blue/green Kk−1K_{k-1} that avoids a blue K4K_4 (and hence, a red/blue K4K_4) and a green K5K_5 (and hence, a red/green K5K_5). As there are not enough vertices to form a blue/green KkK_k, it follows that gr23(K4,K5,Kk)≥kgr^{3}_{2}(K_4,K_5,K_k) \ge k. To prove the reverse inequality, consider a Gallai 3-coloring of KkK_k that avoids a red/blue K4K_4, a red/green K5K_5, and a blue/green KkK_k. It cannot lack a red edge, or it would form a blue/green KkK_k. So, let xx be a vertex that is incident with a red edge. Let Nr(x)N_r(x), Nb(x)N_b(x), and Ng(x)N_g(x) be the red, blue, and green neighborhoods of xx, respectively. If either of Nr(x)N_r(x) or Nb(x)N_b(x) contains a red or blue edge, then that edge, along with xx and a single vertex from the other neighborhood, forms a red/blue K4K_4. So, both Nr(x)N_r(x) and Nb(x)N_b(x) induce complete green subgraphs. If both of Nr(x)N_r(x) and Ng(x)N_g(x) contain red or green edges, then those edges, along with xx, form a red/green K5K_5. So, either Ng(x)N_g(x) induces a blue complete subgraph or ∣Nr(x)∣=1|N_r(x)|=1. If Ng(x)N_g(x) only contains blue edges, then ∣Ng(x)∣≤3|N_g(x)|\le3 (otherwise a blue K4K_4 exists). Then

∣Nr(x)∪Nb(x)∣≥k−4≥11.|N_r(x)\cup N_b(x)|\ge k-4\ge11.

By the pigeonhole principle, one of Nr(x)N_r(x) and Nb(x)N_b(x) contains a green K6K_6. If ∣Nr(x)∣=1|N_r(x)|=1, then ∣Nb(x)∣≤4|N_b(x)|\le4 (since a green K5K_5 is avoided) implies that

∣Ng(x)∣≥k−6≥9.|N_g(x)|\ge k-6\ge9.

Since, r(K3,K4)=9r(K_3,K_4)=9 [8], it follows that the subgraph induced by Ng(x)N_g(x) contains a red/green K3K_3 (which, along with xx and the vertex in Nr(x)N_r(x), forms a red/green K5K_5) or a blue K4K_4. It follows that gr⁡23(K4,K5,Kk)≤k\operatorname{gr}^{3}_{2}(K_4,K_5,K_k)\le k. □

Conclusion

A natural extension of the work contained in this paper is to consider chromatic Gallai-Ramsey numbers of the form gr⁡t−1t(G1,G2,…,Gt)\operatorname{gr}^{t}_{t-1}(G_1,G_2,\ldots,G_t), when t≥4t\ge4. Also, considering graphs other than complete graphs for the arguments leads to many new directions. Also, the star-critical analogues of these numbers may also be considered. Such numbers determine the number of edges that must be added to a critical coloring from a vertex so that the Ramsey property holds. When the arguments are all complete graphs, the weakened star-critical chromatic Gallai-Ramsey number is 1 less than the corresponding weakened chromatic Gallai-Ramsey number (cf., Theorem 3.8 of [2]). So, the interesting cases will be those in which the arguments are not all complete graphs.

Acknowledgements. The first-listed author was funded by a Scholarly Development Assignment Program award from Western Carolina University. Department and Mathematics and Computer Science, Western Carolina University, Cullowhee, NC, USA. Email address: [email protected]

Department and Mathematics and Computer Science, Western Carolina University, Cullowhee, NC, USA. Email address: [email protected]

References

  1. [1]G. Beam and M. Budden, Weakened Gallai-Ramsey numbers, Surv. Math. Appl. 13 (2018), 131–145.
  2. [2]M. Budden, Weakened Ramsey Theory, CRC Press, Boca Raton, 2026.DOI
  3. [3]K. Chung, M. Chung, and C. Liu, A generalization of Ramsey theory for graphs - with stars and complete graphs as forbidden graphs, Congr. Numer. 19 (1977), 155–161.
  4. [4]K. Chung and C. Liu, A generalization of Ramsey theory for graphs, Discrete Math. 21 (1978), 117–127.
  5. [5]P. Erdős, M. Simonovits, and V. Sós, Anti-Ramsey theorems, Colloq. Math. Soc. János Bolyai 10 (1975), 633–643, in Infinite and Finite Sets, (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday) Vol. II, North-Holland, Amsterdam-London, 1975.
  6. [6]T. Gallai, Transitiv orientierbare graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.DOI
  7. [7]J.E. Graver and J. Yackel, Some graph theoretic results associated with Ramsey’s theorem, J. Combin. Theory 4 (1968) 125–175.DOI
  8. [8]R. Greenwood and A. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955), 1–7.DOI
  9. [9]C. Grinstead and S. Roberts, On the Ramsey numbers R(3,8) and R(3,9), J. Combin. Theory Ser. B 33 (1982) 27–51.DOI
  10. [10]A. Gyárfás and G. Simonyi, Edge colorings of complete graphs without tricolored triangles, J. Graph Theory 46(3) (2004), 211–216.DOI
  11. [11]H. Harborth and M. Möller, Weakened Ramsey numbers, Discrete Appl. Math. 95 (1999), 279–284.DOI
  12. [12]M. Jacobson, On Various Extensions of Ramsey Theory, Ph.D. thesis, Emory University, 1980.
  13. [13]M. Jacobson, On a generalization of Ramsey theory, Discrete Math. 38 (1982), 191–195.DOI
  14. [14]J.G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull. 8 (1965), 575–584.DOI
  15. [15]J.G. Kalbfleisch, Chromatic Graphs and Ramsey’s Theorem, Ph.D. thesis, University of Waterloo, January 1966.
  16. [16]G. Kéry, On a theorem of Ramsey (in Hungarian), Matematikai Lapok 15 (1964) 204–224.
  17. [17]A. Khamseh and G. Omidi, A generalization of Ramsey theory for stars and one matching, Math. Reports 19 (69) (2017), 85–92.
  18. [18]C. Liu and K. Chung, A Generalization of Ramsey Theory for Graphs, Department of Computer Science, University of Illinois at Urbana-Champaign, 1977.
  19. [19]C. Magnant and P. Salehi Nowbandegani, Topics in Gallai-Ramsey Theory, Springer Briefs in Mathematics, Springer, Cham, 2020.DOI
  20. [20]B.D. McKay and S. Radziszowski, R(4, 5) = 25, J. Graph Theory 19 (1995), 309–322.DOI
  21. [21]B.D. McKay and K. M. Zhang, The value of the Ramsey number R(3,8), J. Graph Theory 16 (1992) 99–105.DOI
  22. [22]S. Radziszowski, Small Ramsey Numbers - Revision 18, Electron. J. Combin. DS1.18 (2026), 149 pages.
  23. [23]A. Yi and Z. Luo, The s-chromatic Ramsey number for stars, Discrete Math. Theor. Comput. Sci. 28 (3) (2026), #5 (12 pages).DOI

Paper details

vlnc:W_tew4aty4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents