Ramsey and Gallai-Ramsey numbers for linear forests and kipas¹¹1Supported by the National Natural Science Foundation of China (Nos. 12201375, 12061059).

Ping Li²²2Corresponding author: School of Mathematics and Statistics, Shaanxi Normal University, Xi’an, Shaanxi, China. [email protected], Yaping Mao ³³3JSPS International Research Fellow: Faculty of Environment and Information Sciences, Yokohama National University, 79-2 Tokiwadai, Hodogaya-ku, Yokohama 240-8501, Japan. [email protected] , Ingo Schiermeyer ⁴⁴4Institut für Diskrete Mathematik und Algebra, Technische Universität Bergakademie Freiberg, 09596 Freiberg, Germany. [email protected] , Yifan Yao ⁵⁵5 School of Mathematics and Statistics, Qinghai Normal University, Xining, Qinghai 810008, China. [email protected]

Abstract

For two graphs $G,H$ , the Ramsey number $r(G,H)$ is the minimum integer $n$ such that any red/blue edge-coloring of $K_{n}$ contains either a red copy of $G$ or a blue copy of $H$ . For two graphs $G,H$ , the Gallai-Ramsey number $\operatorname{gr}_{k}(G:H)$ is defined as the minimum integer $n$ such that any $k$ -edge-coloring of $K_{n}$ must contain either a rainbow copy of $G$ or a monochromatic copy of $H$ . In this paper, the classical Ramsey numbers of linear forest versus kipas are obtained. We obtain the exact values of $\operatorname{gr}_{k}(G:H)$ , where $H$ is either a path or a kipas and $G\in\{K_{1,3},P_{4}^{+},P_{5}\}$ and $P_{4}^{+}$ is the graph consisting of $P_{4}$ with one extra edge incident with inner vertex.
Keywords: Ramsey number; Gallai-ramsey number; Path; Kipas

1 Introduction

All graphs considered in this paper are undirected, finite and simple. We refer to the book [1] for graph theoretical notation and terminology not described here. For a graph $G$ , let $V(G)$ , $E(G)$ , $|G|$ , $e(G)$ and $\delta(G)$ denote the set of vertices, the set of edges, the number of vertices, the number of edges and the minimum degree of $G$ , respectively. We also call $|G|$ and $e(G)$ the order and the size of $G$ , respectively. The neighborhood set of a vertex $v\in V(G)$ is $N_{G}(v)=\{u\in V(G)\,|\,uv\in E(G)\}$ , and its closed neighborhood set is $N_{G}[v]=N_{G}(v)\cup\{v\}$ . For two subsets $X$ and $Y$ of $V(G)$ we denote by $E_{G}[X,Y]$ the set of edges of $G$ with one endpoint in $X$ and the other endpoint in $Y$ . Let $N_{G}(v,S)=N_{G}(v)\cap S$ . Let $\overline{G}$ be the complement of $G$ . For any integers $m<n$ , we use the convenient notation $[m,n]$ for the set $\{m,m+1,\cdots,n-1,n\}$ , specially, we denote $[n]$ as $[1,n]$ . For a path $P_{n}=v_{1}v_{2}\ldots v_{n}$ , we call $v_{\lceil\frac{n}{2}\rceil}$ and $v_{\lceil\frac{n+1}{2}\rceil}$ center vertices of $P_{n}$ . For a graph $H$ and a vertex $v\notin V(H)$ , let $v\vee H$ be a graph obtained from $H$ by connecting each vertex of $H$ and $v$ . If $H$ is a path of order $n$ , then $v\vee H$ is called a kipas with center $v$ , and denote it by $\widehat{K}_{n}$ .

Definition 1.

For two graphs $G,H$ , the Ramsey number $r(G,H)$ is the minimum integer $n$ such that any red/blue edge-coloring of $K_{n}$ contains either a red copy of $G$ or a blue copy of $H$ .

Definition 2.

Let $\mathcal{F}$ be a set of graphs. The Ramsey number $r(G,\mathcal{F})$ is the minimum integer $n$ such that any red/blue edge-coloring of $K_{n}$ contains either a red copy of $G$ or a blue copy of graph in $\mathcal{F}$ .

For more details on Ramsey numbers, we refer to the survey paper [23] and some papers [2, 4, 5, 10].

1.1 Ramsey and Gallai-Ramsey numbers

The Gallai- $k$ -coloring (or Gallai-coloring for short) is a $k$ -edge-coloring of a complete graph without rainbow triangles. The following result gives the structure of Gallai-coloring.

Theorem 1.1.

[9, 13] In any rainbow triangle free edge-coloring of a complete graph, the vertex set can be partitioned into at least two parts such that between the parts there is a total of at most two colors, and between each pair of parts there is only one color on the edges.

Let $g^{q}_{k}(p)$ be the smallest positive integer $n$ such that every Gallai- $k$ -coloring of $K_{n}$ contains a $K_{p}$ receiving at most $q$ distinct colors. In [6], Fox et al. studied the integer $p$ when $n$ is fixed, and got the following asymptotic result.

Theorem 1.2.

[6] Let $k$ and $q$ be fixed positive integers with $q\leq k$ . Every Gallai- $k$ -coloring of $K_{n}$ contains a set of order $\Omega(n^{\binom{q}{2}/\binom{k}{2}}\log_{2}^{c_{k,q}}n)$ which uses at most $q$ colors, where $c_{k,q}$ is only depending on $k$ and $q$ . Moreover, this bound is tight apart from the constant factor.

Note that $g^{1}_{k}(p)$ is the minimum integer $n$ such that every Gallai- $k$ -coloring of $K_{n}$ contains a monochromatic $K_{p}$ . The $g^{1}_{k}(p)$ is also denoted by $\operatorname{gr}_{k}(K_{3}:K_{p})$ .

Definition 3.

For two graphs $G,H$ , the Gallai-Ramsey number $\operatorname{gr}_{k}(G:H)$ is defined as the minimum integer $N$ such that for any $n\geq N$ and any exact $k$ -edge-coloring (using $k$ colors) of $K_{n}$ must contain either a rainbow copy of $G$ or a monochromatic copy of $H$ .

Definition 4.

Define $\operatorname{gr}^{\prime}_{k}(G:H)$ as the minimum integer $N$ such that for all $n\geq N$ , every edge-coloring of $K_{n}$ using at most $k$ colors contains either a rainbow copy of $G$ or a monochromatic copy of $H$ .

It is obvious that $\operatorname{gr}^{\prime}_{k}(G:H)\leq\max\{\operatorname{gr}_{i}(G:H):1\leq i\leq k\}$ . On the other hand, we have that $\operatorname{gr}^{\prime}_{k}(G:H)\geq\max\{\operatorname{gr}_{i}(G:H):1\leq i\leq k\}$ . Otherwise, there exists an integer $k^{\prime}$ ( $1\leq k^{\prime}\leq k$ ) such that $\operatorname{gr}_{k^{\prime}}(G:H)>\operatorname{gr}^{\prime}_{k}(G:H)$ . By the definition of $\operatorname{gr}_{k^{\prime}}(G:H)$ , there is a $k^{\prime}$ -edge-coloring of $K_{\operatorname{gr}_{k^{\prime}}(G:H)-1}$ such that there is neither rainbow copy of $G$ nor monochromatic copy of $H$ . However, $\operatorname{gr}_{k^{\prime}}(G:H)-1\geq\operatorname{gr}^{\prime}_{k}(G:H)$ , which implies that there is either a rainbow copy of $G$ or a monochromatic copy of $H$ in any $k^{\prime}$ -edge-coloring of $K_{\operatorname{gr}_{k^{\prime}}(G:H)-1}$ , a contradiction. Therefore, $\operatorname{gr}^{\prime}_{k}(G:H)=\max\{\operatorname{gr}_{i}(G:H):1\leq i\leq k\}$ , and we only need to talk about the parameter $\operatorname{gr}_{k}(G:H)$ .

Fox et al. [6] proposed the following conjecture.

Conjecture 1.

[6] For integers $k\geq 3$ and $p\geq 3$ ,

\operatorname{gr}_{k}(K_{3}:K_{p})=\left\{\begin{array}[]{ll}(r(K_{p},K_{p})-1)^{k/2}+1,&\mbox{if }n\mbox{ is even},\\ (p-1)(r(K_{p},K_{p})-1)^{(k-1)/2}+1,&\mbox{if }n\mbox{ is odd}.\\ \end{array}\right.

Chung and Graham [3] and Gyárfás et al. [12] proved the case $p=3$ , Liu et al. [17] proved the case $p=4$ , and Magnant and Schiermeyer [21] proved the case $k=5$ . For more details on the Gallai-Ramsey numbers, we refer to a dynamic survey [8] and the recent book [20].

1.2 Structural theorems and our methods

The Gallai- $k$ -coloring, a $k$ -edge-coloring of $K_{n}$ without rainbow $K_{3}$ , has an interesting structure. Fujita and Magnant [7] consider the structures of $k$ -edge-coloring of $K_{n}$ without rainbow $S_{3}^{+}$ , where $S_{3}^{+}$ is a graph obtain from $K_{3}$ by adding a pendent edge. Thomason and Wagner [25] got the structures of $k$ -edge-coloring of $K_{n}$ without rainbow $P_{5}$ . In addition, Gyárfás et al. [11] investigated the local Ramsey number of stars, which implies the structures of $k$ -edge-coloring of $K_{n}$ without a rainbow star $K_{1,3}$ or a rainbow tree $P_{4}^{+}$ , respectively, where $P_{4}^{+}$ is the graph consisting of $P_{4}$ with one extra edge incident with a center vertex.

In this paper, we study the Gallai-Ramsey number $\operatorname{gr}_{k}(G:H)$ , where $G\in\{K_{1,3},P_{5},P_{4}^{+}\}$ and $H$ is a path or a kipas. The following are the structures of $k$ -edge-colored $K_{n}$ without rainbow $P_{5},K_{1,3}$ and $P_{4}^{+}$ , respectively.

Given an edge coloring of $K_{n}$ , let $E_{j}$ be the set of edges colored $j$ and let $V_{j}$ be the vertices at which an edge of color $j$ appears. The following are the structures of $k$ -edge-coloring of $K_{n}$ without a rainbow $P_{5}$ .

Theorem 1.3.

[25] Let $k,n$ be two integers with $k\geq 4$ and $n\geq 5$ . Let $K_{n}$ be a $k$ -edge-colored graph so that it contains no rainbow $P_{5}$ . Then, after renumbering the colors, one of the following must hold:

$(i)$ color 1 is dominant, meaning that the sets $V_{j}$ , $j\geq 2$ , are disjoint;
$(ii)$ $K_{n}-a$ is monochromatic for some vertex $a$ ;
$(iii)$ there are three vertices $a,b,c$ such that $E_{2}=\{ab\}$ , $E_{3}=\{ac\}$ , $E_{4}$ contains $bc$ plus perhaps some edges incident with $a$ , and every other edge is in $E_{1}$ ;
$(iv)$ there are four vertices $a,b,c,d$ such that $\{ab\}\subseteq E_{2}\subseteq\{ab,cd\}$ , $E_{3}=\{ac,bd\}$ , $E_{4}=\{ad,bc\}$ and every other edge is in $E_{1}$ ;
$(v)$ $n=5$ , $V(K_{n})=\{a,b,c,d,e\}$ , $E_{1}=\{ad,ae,bc\}$ , $E_{2}=\{bd,be,ac\}$ , $E_{3}=\{cd,ce,ab\}$ and $E_{4}=\{de\}$ .

Let $G_{1}(n)$ be a $3$ -edge-coloring of $K_{n}$ such that $V(K_{n})$ can be partitioned into three parts $V_{1},V_{2},V_{3}$ (at most one of them is empty) such that each edge of $G[V_{1}]$ is colored by either $1$ or $3$ , each edge of $G[V_{2}]$ is colored by either $1$ or $2$ , and each edge of $G[V_{3}]$ is colored by either $2$ or $3$ . Moreover, each edge between $V_{1},V_{2}$ is colored by $1$ , each edge between $V_{2},V_{3}$ is colored by $2$ and each edge between $V_{1},V_{3}$ is colored by $3$ .

Let $G_{2}(n)$ be a $4$ -edge-coloring of $K_{n}$ such that there is exactly one edge, say $xy$ , having color $2$ . All other edges incident with $x$ are colored by $3$ , and all other edges incident with $y$ are colored by $4$ . All edges not incident to vertices $x,y$ have color $1$ .

Let $G_{3}(n)$ be a $4$ -edge-coloring of $K_{n}$ such that there exists a rainbow $K_{3}$ (say the vertices in the triangle are $a,b,c$ , where $ab$ has color $2$ , $bc$ has color $3$ and $ac$ has color $4$ ). In addition, any other edge has color $1$ .

Remark 1.1.

If $\Gamma$ is an edge-coloring of $\{(ii),(iii),(iv),(v),G_{2}(n),G_{3}(n)\}$ of $K_{n}$ , then the graph induced by edges with color $i\geq 2$ is a star forest.

The following are the structures of $k$ -edge-coloring of $K_{n}$ without a rainbow $K_{1,3}$ .

Theorem 1.4 ([11]).

For positive integers $k\geq 3$ and $n$ , if $G$ is a $k$ -edge-coloring of $K_{n}$ without rainbow $K_{1,3}$ , then after renumbering the colors, one of the following holds.

$(I1)$ $k=3$ and $G\cong G_{1}(n)$ ;

$(I2)$ $k\geq 4$ and Item $(i)$ in Theorem 1.3 holds.

The following are the structures of $k$ -edge-coloring of $K_{n}$ without rainbow $P_{4}^{+}$ .

Theorem 1.5 ([11]).

For positive integers $k\geq 4$ and $n$ , if $G$ is a $k$ -edge-coloring of $K_{n}$ without rainbow $P_{4}^{+}$ , then after renumbering the colors, one of the following holds.

$(J1)$ $k=4$ and $G\in\{G_{2}(n),G_{3}(n)\}$ ;

$(J2)$ $k\geq 4$ and Item $(i)$ in Theorem 1.3 holds.

Recall Theorem 1.1 and definition of $\operatorname{gr}_{k}(K_{3}:H)$ , the structure of Gallai-coloring is important for $\operatorname{gr}_{k}(K_{3}:H)$ . Analogously, the structures of $k$ -edge-colorings in Theorem 1.3 is important for $\operatorname{gr}_{k}(P_{5}:H)$ . However, there are five structures, and it is complicated if we consider the five structures at the same time. Observe that the structures $(ii)-(iv)$ are simple since they contain a large monochromatic complete graph (the monochromatic complete graph can obtained by deleting at most three vertices), and structure $(v)$ is simple since there are only five vertices. Therefore, the structures $(i)$ is very important for $\operatorname{gr}_{k}(P_{5}:H)$ . Similarly, in Theorem 1.4, the structures $G_{1}(n)$ and $(i)$ are important; in Theorem 1.5, the structure $(i)$ is important and structures $G_{2}(n)$ and $G_{3}(n)$ are clear. By above discussion, $G_{1}(n)$ and $(i)$ are key structures in $k$ -edge-colored $K_{n}$ without rainbow $P_{5},K_{1,3}$ or $P_{4}^{+}$ .

Firstly, we observe the structure $(i)$ . Suppose $k\geq 3$ . It is clear that $K_{n}$ can be partitioned into $k-1$ parts $V_{1},\cdots,V_{k-1}$ such that each edge between different parts is colored by $1$ , and each edge of $G[V_{i-1}]$ is colored by either $1$ or $i$ . Therefore, $G[V_{i}]$ contains all edges of color $i+1$ and $|V_{i}|\geq 2$ for $i\in[k-1]$ . We denote the set of all such $k$ -edge-colorings on $K_{n}$ by $\mathcal{B}_{k}(n)$ .

Definition 5.

Let $b_{k}(H)$ be the minimum number $n$ such that any edge-coloring $\Gamma\in\mathcal{B}_{k}(n)$ of $K_{n}$ contains a monochromatic $H$ .

For the structure $G_{1}(n)$ , $V(K_{n})$ can be partitioned into three parts $V_{1},V_{2},V_{3}$ as the definition, and at most one part is empty. If there is an empty part, then $G_{1}(n)\in\mathcal{B}_{3}(n)$ . Thus, we only consider that $V_{1},V_{2},V_{3}$ are all nonempty sets. We denote the set of all such 3-edge-colorings on $K_{n}$ by $\mathcal{T}(n)$ .

Definition 6.

Let $t(H)$ be the minimum number $n$ such that any edge-coloring $\Gamma\in\mathcal{T}(n)$ of $K_{n}$ contains a monochromatic $H$ .

Remark 1.2.

In order to determine the $\operatorname{gr}_{k}(G:H)$ , where $G\in\{P_{5},K_{1,3},P_{4}^{+}\}$ , the main work is to determine $b_{k}(H)$ or $t(H)$ . It is easy to verify whether $K_{n}$ contains a monochromatic copy of $H$ under the other structures.

1.3 Progress and our results

Li et al. [18] got some exact values of $\operatorname{gr}_{k}(P_{5}:K_{t})$ for small $t$ and bounds for general $t$ . Recently, Wei et al. [26] got the exact values of $\operatorname{gr}_{k}(P_{5}:H)\ (k\geq 3)$ for small $t$ and upper and lower bounds for general $t$ , where $H$ is either a general fan or a general wheel graph. The motivation of this paper is whether we can obtain exact values for $\operatorname{gr}_{k}(P_{5}:H)\ (k\geq 4)$ such that $H$ is not just a graph but belongs to a class of graphs.

In this paper, we first study the new parameters $b_{k}(P_{n}),t(P_{n}),b_{k}(\widehat{K}_{n})$ and $t(\widehat{K}_{n})$ , and further get the exact values of $\operatorname{gr}_{k}(G:P_{n})$ and $\operatorname{gr}_{k}(G:\widehat{K}_{n})$ , where $G\in\{P_{5},K_{1,3},P_{4}^{+}\}$ .

We call a linear forest a $k$ -linear forest if any component of the linear forest is a path of order at least $k$ . We first get a classical Ramsey number for $\widehat{K}_{n}$ and the set of $3$ -linear forests, and the result is useful and will be used in Section 5.

Theorem 1.6.

If $2\leq m\leq\frac{n}{2}$ and $\mathcal{L}$ is the set of linear forest $L$ of size at least $m$ , then

r(\widehat{K}_{n},\mathcal{L})=n+\lceil m/2\rceil.

In addition, if $6\leq m\leq\frac{n}{2}$ and $\mathcal{L}^{\prime}$ is the set of $3$ -linear forest $L$ of size at least $m$ , then

r(\widehat{K}_{n},\mathcal{L}^{\prime})=n+\lceil m/2\rceil.

The Gallai-Ramsey numbers are list as follows.

Theorem 1.7.

If $n\geq k\geq 4$ , then

\operatorname{gr}_{k}(P_{5}:P_{n})=\left\{\begin{array}[]{ll}n+1,&{\rm if}~{}2(k-1)\leq n\leq 4(k-2)+1,\\ \left\lceil\frac{3n-3}{2}\right\rceil,&{\rm if}~{}n>4(k-2)+1.\\ \end{array}\right.

Theorem 1.8.

If $n\geq k\geq 4$ , then

\operatorname{gr}_{k}(P_{4}^{+}:P_{n})=\left\{\begin{array}[]{ll}n+2,&{\rm if}~{}k=4~{}{\rm and}~{}2(k-1)\leq n\leq 4(k-2)+1,\\ n,&{\rm if}~{}k\geq 5~{}{\rm and}~{}2(k-1)\leq n\leq 4(k-2)+1,\\ \left\lceil\frac{3n-3}{2}\right\rceil,&{\rm otherwise}.\\ \end{array}\right.

Theorem 1.9.

$(1)$ If $n\geq 2(k-1)$ and $k\geq 4$ , then

\operatorname{gr}_{k}(K_{1,3}:P_{n})=\left\{\begin{array}[]{ll}n,&{\rm if}~{}2(k-1)\leq n\leq 4(k-2)+1,\\ \left\lceil\frac{3n-3}{2}\right\rceil,&{\rm if}~{}n>4(k-2)+1.\\ \end{array}\right.

$(2)$ If $k=3$ and $n\geq 4$ , then

\operatorname{gr}_{k}(K_{1,3}:P_{n})=\left\{\begin{array}[]{ll}\frac{3n}{2}-1,&{\rm if}~{}n\mbox{ is even},\\ \frac{3n-1}{2},&{\rm if}~{}n\mbox{ is odd }.\end{array}\right.

Remark 1.3.

We do not discuss $\operatorname{gr}_{k}(P_{5}:P_{n}),\operatorname{gr}_{k}(P_{4}^{+}:P_{n})$ and $\operatorname{gr}_{k}(K_{1,3}:P_{n})$ when $k\geq 4$ and $n<2(k-1)$ , since it is easily to obtain. In fact, if $k\geq 4$ and $n<2(k-1)$ , then $K_{n}$ must contain a monochromatic $P_{n}$ when the edge-coloring $\Gamma$ of $K_{n}$ belongs to $\mathcal{B}_{k}(n)$ . However, other edge-colorings $G_{2}(N),G_{3}(N),(ii),(iii),(iv)$ and $(v)$ are simple.

Theorem 1.10.

For $n\geq 5$ , we have that $\operatorname{gr}_{3}(K_{1,3}:\widehat{K}_{n})=\left\lfloor\frac{5n}{2}\right\rfloor$ if $n$ is odd, and $\left\lfloor\frac{5n}{2}\right\rfloor-1\leq\operatorname{gr}_{3}(K_{1,3}:\widehat{K}_{n})\leq\left\lfloor\frac{5n}{2}\right\rfloor$ if $n$ is even.

2 Preliminaries

As we know, the study of Gallai-Ramsey numbers deeply depend on the classical Ramsey number. Therefore, we list some useful classical Ramsey numbers in this section, which can be found in the survey paper [23].

Theorem 2.1.

[10] If $2\leq m\leq n$ , then $r(P_{n},P_{m})=n+\left\lfloor m/2\right\rfloor-1$ .

The following theorem is a generalization of Theorem 2.1.

Theorem 2.2.

[5] Suppose $L_{1},L_{2}$ are $2$ -linear forests having $j_{1},j_{2}$ components of odd order, respectively. Then

r(L_{1},L_{2})=\max\left\{|L_{1}|+\left\lfloor\frac{|L_{2}|-j_{2}}{2}\right\rfloor-1,|L_{2}|+\left\lfloor\frac{|L_{1}|-j_{1}}{2}\right\rfloor-1\right\}.

Theorem 2.3.

[22] $r(P_{m},K_{1,n})=m+n-1$ if $n\equiv 1\pmod{n-1}$ , and $r(P_{m},K_{1,n})\leq m+n-2$ otherwise.

Theorem 2.4.

[14] If $m,n\geq 2$ , then

r(K_{1,n},K_{1,m})=\left\{\begin{array}[]{ll}m+n-1,&\mbox{ if }m,n\mbox{ are even},\\ m+n,&\mbox{ otherwise}.\\ \end{array}\right.

Li et al. [16] got a closing gap on path-kipas Ramsey numbers.

Theorem 2.5.

[16] For $m\leq 2n-1$ and $m,n\geq 2$ , we have

r(P_{n},\widehat{K}_{m})=\max\left\{2n-1,\left\lceil\frac{3m}{2}\right\rceil-1,2\left\lfloor\frac{m}{2}\right\rfloor+n-2\right\}.

Salman and Broersma [24] obtained the following result for path-kipas Ramsey numbers.

Theorem 2.6.

[24] If $n\geq 4$ and $m\geq 2n-2$ , then $r(P_{n},\widehat{K}_{m})\leq m+n-1$ .

Li et al. [15] obtained an exact formula for all star-kipas Ramsey numbers.

Theorem 2.7.

[15] Let $n,m\geq 2$ be two integers.

$(1)$ If $m\geq 2n$ , then

r(K_{1,n},\widehat{K}_{m})=\left\{\begin{array}[]{ll}m+n-1,&\mbox{ if }m,n\mbox{ are even},\\ m+n,&\mbox{ otherwise}.\\ \end{array}\right.

$(2)$ If $m\leq 2n-1$ , then

r(K_{1,n},\widehat{K}_{m})=\left\{\begin{array}[]{ll}2n+\lfloor\frac{m}{2}\rfloor-1,&\mbox{ if }m,\lfloor\frac{m}{2}\rfloor\mbox{ are even},\\ 2n+\lfloor\frac{m}{2}\rfloor,&\mbox{ otherwise}.\\ \end{array}\right.

The following is a result about decomposition of the complete graph.

Theorem 2.8.

[19] For $n\geq 1$ , $K_{2n+1}$ can be decomposed into $n$ edge-disjoint Hamiltonian cycles; $K_{2n+2}$ can be decomposed into $n$ edge-disjoint Hamiltonian cycles and a perfect matching.

The following result will be used in the subsequent proofs, and we give a simple proof here, although it may be proved somewhere.

Lemma 2.1.

Suppose that $G$ is a complete $r$ -partite graph with parts $V_{1},\ldots,V_{r}$ and $V_{r}$ is one maximum part.

1.

If $\sum_{i\in[r-1]}|V_{i}|\geq|V_{r}|$ , then $G$ contains a Hamiltonian cycle.
2.

If $\sum_{i\in[r-1]}|V_{i}|=|V_{r}|-1$ , $G$ contains a Hamiltonian path.

Proof.

The result is true for bipartite graphs. So, suppose $r\geq 3$ . Without loss of generality, let $|V_{1}|\leq|V_{2}|\leq\ldots\leq|V_{r}|$ . Then there exists an $s\in[r]$ such that $|V_{s-1}|<|V_{s}|=\ldots=|V_{t}|$ . The proof proceeds by induction on $|G|$ . If $|G|=3$ , then the result holds obviously. If $|V_{r}|=1$ , then $G$ is a complete graph and the result follows. So, suppose that $|G|\geq 4$ and $|V_{r}|>1$ . Choose a vertex $v_{i}$ from $V_{i}$ for $i\in[s,r]$ . Let $U_{i}=V_{i}$ for $i<s$ and $U_{i}=V_{i}-v_{i}$ for $i\in[s,r]$ , and let $G^{\prime}=G-\{v_{s},\ldots,v_{r}\}$ . Then $U_{r}$ is a maximum part in $G^{\prime}$ . Since $|V_{i}|\geq 2$ , each $U_{i}$ is nonempty.

We prove the first statement. Since $\sum_{i\in[r-1]}|V_{i}|\geq|V_{r}|$ , it follows that $\sum_{i\in[r-1]}|U_{i}|\geq|U_{r}|$ . By induction, $G^{\prime}$ contains a Hamiltonian cycle $C$ . Note that $v_{s},\ldots,v_{r}$ induces a complete graph. Since $r\geq 3$ , there are three integer $i,j,k$ such that there are two adjacent edges $xy$ and $yz$ of $G$ with $x\in V_{i}$ , $y\in V_{j}$ and $z\in V_{k}$ . If $r=s$ , then we can assume that $r\notin\{i,j\}$ , and hence $(C\backslash\{xy\})\cup\{xv_{r},yv_{r}\}$ is a Hamiltonian cycle of $G$ . If $s<r-1$ (resp. $s=r-1$ ), then there is a cycle $C^{\prime}=v_{s}v_{s+1}\ldots v_{r}v_{s}$ in $G$ (resp. an edge $v_{r-1}v_{r}$ of $G$ ). There is an integer of $i,j,k$ which is not in $\{r-1,r\}$ (say $i\notin\{r-1,r\}$ ), and one of $r-1,r$ is not equal to $j$ (without loss of generality, suppose that $j\neq r$ ). Then $(C\backslash\{xy\})\cup(C^{\prime}\backslash\{v_{r}v_{r-1}\})\cup\{xv_{r-1},yv_{r}\}$ (resp. $(C\backslash\{xy\})\cup\{v_{r-1}v_{r},xv_{r-1},yv_{r}\}$ ) is a Hamiltonian of $G$ .

Now we prove the second statement. In this case, $s=r$ and $\sum_{i\in[r-1]}|U_{i}|=|U_{r}|$ . So, $G^{\prime}$ has a Hamiltonian cycle $C^{*}$ by the first result. Let $ww^{\prime}\in E(C^{*})$ and suppose that $w\notin V_{r}$ by symmetry. Then $(C^{*}\backslash\{ww^{\prime}\})\cup\{wv_{r}\}$ is a Hamiltonian path of $G$ . ∎

3 Technique results and the proof of Theorem 1.6

In this section, we prove two critical lemmas, which will be used in Section 5.

Lemma 3.1.

Suppose that $n\geq 4$ , $a\in\{1,2\}$ and $N=n+a$ . If $\Gamma$ is a red/blue edge-coloring of $K_{N}$ such that $K_{N}$ does not contain a red copy of $\widehat{K}_{n}$ , then the following results hold.

$(i)$ If $a=1$ , then $K_{N}$ contains either a blue copy of $2P_{2}$ or a blue copy of $P_{3}$ .

$(ii)$ If $a=2$ and $n\geq 5$ , then $K_{N}$ contains either a blue copy of $2P_{3}$ , or a blue copy of $P_{5}$ , or a blue copy of vertex-disjoint $P_{4}$ and $P_{2}$ .

Proof.

Suppose that $R,B$ are the graphs with the common vertex set $V=V(K_{N})$ and their edges sets are red edges and blue edges, respectively. Note that $R$ does not contains a copy of $\widehat{K}_{n}$ . For convenience, we use $P_{2}\cup P_{4}$ to denote vertex-disjoint $P_{4}$ and $P_{2}$ throughout this proof.

$(i)$ For $a=1$ , if $\delta(B)\geq 1$ , then $B$ contains either a $2P_{2}$ or a $P_{3}$ , since $n\geq 4$ . If $\delta(B)=0$ , then there exists a vertex in $B$ such that $d_{B}(v)=0$ , and hence $R-v$ does not contain a Hamiltonian path (otherwise there is a red $\widehat{K}_{n}$ , a contradiction). Suppose that $P$ is the maximum path of $R-v$ with endpoints $a,b$ . Then $V(R)-\{v\}-V(P)\neq\emptyset$ . By the maximality of $P$ , we have $ua,ub\in E(B)$ for each $u\in V(R)-\{v\}-V(P)$ , and hence $B$ contains a $P_{3}$ .

$(ii)$ For $a=2$ , suppose to the contrary that $B$ does not contain $2P_{3}$ , $P_{5}$ or $P_{4}\cup P_{2}$ . We first assume that $B$ has at most one vertex of degree greater than one (if the vertex exists, denote it by $w$ ). It is clear that $|B-w|=n+1$ and $\Delta(B-w)\leq 1$ if $w$ exists. If $w$ exists and $B-w$ contains a perfect matching $M$ , then there is a blue $P_{5}$ with center $w$ . Otherwise, there are two vertex $u,v$ of $K_{N}$ such that $u$ is an isolated vertex of $B-v$ and $\Delta(B-v)\leq 1$ . In fact, if $w$ exists and $B-w$ does not contain a perfect matching $M$ , then there is an isolated vertex $u$ of $B-w$ (we can see $w$ as $v$ ) and $\Delta(B-v)\leq 1$ ; if $w$ does not exist, then $\Delta(B-w)\leq 1$ , and for an edge $xy$ of $B$ , $x$ is an isolated vertex of $B-y$ (we can see $x,y$ as $u,v$ , respectively). Hence, the vertices $u,v$ are obtained. Let $V^{\prime}=V-\{u,v\}$ and $R^{\prime}=R-\{u,v\}$ . Then $u\vee V^{\prime}$ is a red star. Since $\Delta(B-\{u,v\})\leq 1$ , it follows that $\delta(R^{\prime})\geq|V^{\prime}|-2$ . Since $|V^{\prime}|=n\geq 5$ , by Dirac’s Theorem, $R^{\prime}$ contains a Hamiltonian path $P$ . Hence, $u\vee P$ is a red $\widehat{K}_{n}$ , a contradiction.

Now we assume that there are at least two vertices, say $z_{1},z_{2}$ , of degree at least two in $B$ . Without loss of generality, we can choose $z_{1},z_{2}$ such that $d_{B}(z_{1})+d_{B}(z_{2})$ is as large as possible. We use $E_{u}$ to denote the graph induced by blue edges incident with $u$ . If $N_{B}(z_{1})\cap N_{B}(z_{2})=\emptyset$ , then $E_{z_{1}}\cup E_{z_{2}}$ contains a $2P_{3}$ , unless $E_{z_{1}}\cup E_{z_{2}}$ is a double star. If $|N_{B}(z_{1})\cap N_{B}(z_{2})|=1$ , then $E_{z_{1}}\cup E_{z_{2}}$ contains a $P_{5}$ , unless $E_{z_{1}}\cup E_{z_{2}}$ is a graph obtained form $K_{1,k}$ , $k\geq 2$ , by adding an edge of $\overline{K_{1,k}}$ (the resulting graph is denoted by $K_{1,k}^{+}$ ). If $|N_{B}(z_{1})\cap N_{B}(z_{2})|=2$ , then $E_{z_{1}}\cup E_{z_{2}}$ contains a $P_{5}$ , unless $E_{z_{1}}\cup E_{z_{2}}$ is either a $K_{4}$ , or a $K_{4}^{-}$ , or a $C_{4}$ , where $K_{4}^{-}$ is a graph obtained from $K_{4}$ by deleting an edge. If $|N_{B}(z_{1})\cap N_{B}(z_{2})|=3$ , then $E_{z_{1}}\cup E_{z_{2}}$ contains a $P_{5}$ . Recall that $B$ does not contain $2P_{3},P_{5}$ or $P_{2}\cup P_{4}$ by assumption. Hence, either $E_{z_{1}}\cup E_{z_{2}}$ is a double star or $E_{z_{1}}\cup E_{z_{2}}\in\{K_{1,k}^{+},K_{4},K_{4}^{-},C_{4}\}$ . For convenience, let $\widetilde{H}$ denote the subgraph of $B$ induced by $E_{z_{1}}\cup E_{z_{2}}$ . Then either $\widetilde{H}$ is a double star or $\widetilde{H}\in\{K_{1,k}^{+},K_{4},K_{4}^{-},C_{4}\}$ .

If $\widetilde{H}\in\{K_{4},K_{4}^{-},C_{4}\}$ , then each edge between $U=V(\widetilde{H})$ and $V-U$ is red; otherwise there is a blue $P_{5}$ , a contradiction. It is obvious that $G-U$ is a red complete graph; otherwise there is a blue $P_{2}\cup P_{4}$ , a contradiction. Choose a vertex $u\in V-U$ , $R-\{u,z_{1}\}$ contains a red $P_{n}$ when $n=5$ . For $n\geq 6$ , since $\Delta(B-\{u,z_{1}\})=2$ , it follows that $\delta(R-\{u,z_{1}\})\geq n-3\geq\frac{n}{2}$ . By Dirac’s Theorem, $R-\{u,z_{1}\}$ contains a red $P_{n}$ . Note that $u$ connects every other vertex by red an edge. For $n\geq 5$ , there is a red $\widehat{K}_{n}$ , a contradiction.

If $\widetilde{H}=K_{1,2}^{+}$ (in other words, $\widetilde{H}$ is a triangle), then $d_{B}(z_{1})=d_{B}(z_{2})=2$ . without loss of generality, suppose that $N_{B}(z_{1})\cap N_{B}(z_{2})=\{z\}$ . By the maximality of $d_{B}(z_{1})+d_{B}(z_{2})$ , we have that $d_{B}(z)=2$ . Since $B$ does not contain $2P_{3}$ , $\Delta(B-\{z_{1},z_{2},z\})\leq 1$ . If $n=5$ , then there is a vertex $u$ of $V-\{z_{1},z_{2},z\}$ such that $d_{B}(u)=0$ . Since all edges between $\widetilde{H}$ and $V-u-\widetilde{H}$ are red, it is clear that there is a red $P_{n}$ between $\widetilde{H}$ and $V-u-\widetilde{H}$ . Hence, $u\vee P_{n}$ is a red $\widehat{K}_{n}$ , a contradiction. If $n\geq 6$ , then choose a vertex $u\in V-\{z_{1},z_{2},z\}$ and let $U=V-N_{B}(u)$ . Since $d_{B}(u)\leq 1$ , it follows that $|U|\geq n$ , $\Delta(B[U])\leq 1$ and $u$ connects every vertex of $U$ by an red edge. Then $\delta(R[U])\geq n-3\geq\frac{n}{2}$ . Hence, $R[U]$ contains a Hamiltonian path $P_{n}$ , and $R$ contains a $\widehat{K}_{n}$ , a contradiction.

If $\widetilde{H}=K_{1,k}^{+}$ , where $k\geq 3$ , then we can assume that the edges in $\widetilde{H}$ are

z_{1}x_{1},\ldots,z_{1}x_{k-1},z_{1}z_{2},z_{2}x_{k-1}.

It is obvious that $\Delta(B-z_{1})$ contains only one edge $z_{2}x_{k-1}$ ; otherwise there is either a blue $P_{5}$ or a blue $P_{2}\cup P_{4}$ , a contradiction. Therefore, $\delta(R-\{z_{1},x_{1}\})=n-2\geq\frac{n}{2}$ . By Dirac’s Theorem, $R-\{z_{1},x_{1}\}$ contains a Hamiltonian path $P_{n}$ . Since $x_{1}$ is an isolated vertex in $B$ , it follows that $R$ contains a $\widehat{K}_{n}$ , a contradiction.

If $\widetilde{H}$ is a double star, then $N_{B}(z_{1})\cap N_{B}(z_{2})=\emptyset$ . If $B-\{z_{1},z_{2}\}$ contains an edge $e$ , then $E_{z_{1}}\cup E_{z_{2}}$ contains either a $P_{5}$ or a $P_{2}\cup P_{4}$ , unless $E_{z_{1}}\cup E_{z_{2}}$ is a $P_{4}$ and $e=xy$ (say the edges in $E_{z_{1}}\cup E_{z_{2}}$ are $xz_{1},z_{1}z_{2}$ and $z_{2}y$ ). By the maximality of $d_{B}(z_{1})=d_{B}(z_{2})$ , we have that $d_{B}(x)=d_{B}(y)=d_{B}(z_{1})=d_{B}(z_{2})=2$ , and hence $B$ is a $C_{4}$ with $E(B)=\{z_{1}z_{2},xz_{1},z_{2}y,xy\}$ . Recall that the case have discussed since $B=E_{z_{1}}\cup E_{y}$ is a $C_{4}$ . Therefore, assume that $B-\{z_{1},z_{2}\}$ is the empty graph. Since $|N_{B}(z_{1})-\{z_{2}\}|\cup|N_{B}(z_{2})-\{z_{1}\}|\leq N+2=n$ , either $|N_{B}(z_{1})-\{z_{2}\}|\leq\frac{n}{2}$ or $|N_{B}(z_{2})-\{z_{1}\}|\leq\frac{n}{2}$ (say $|N_{B}(z_{2})-\{z_{1}\}|\leq\frac{n}{2}$ ). Then $|V-z_{1}-N_{B}[z_{2}]|\geq n+2-(\frac{n}{2}+2)=\frac{n}{2}\geq 2$ . Choose two vertices $x,y$ of $V-z_{1}-N_{B}[z_{2}]$ . It is obvious that $x$ connects every vertex of $V-z_{1}$ by a red edge and $yz_{2}$ is a red edge. Note that $R[V-\{z_{1},z_{2},x\}]$ is a complete graph. Hence, there is a Hamiltonian path $Q=P_{n-1}$ of $R[V-\{z_{1},z_{2},x\}]$ with one endpoint $y$ , and hence $Q\cup\{yz_{2}\}$ is a red $P_{n}$ . Now we obtain a red $\widehat{K}_{n}=x\vee(Q\cup\{yz_{2}\})$ , a contradiction. ∎

Let $\mu_{L}$ be the number components of $3$ -linear forest $L$ . Note that $e(L)=|L|-\mu_{L}$ .

Lemma 3.2.

Suppose that $N=n+a$ and $3\leq a\leq\lfloor n/4\rfloor$ . For any red/blue edge-coloring of $K_{N}$ , there is either a red copy of $\widehat{K}_{n}$ or a blue copy of $3$ -linear forest $L$ such that $|L|-\mu_{L}\geq 2a$ .

Proof.

Suppose that $G$ is a red/blue edge-colored $K_{N}$ containing no red $\widehat{K}_{n}$ . Our aim is to obtain a blue $3$ -linear forest $L$ with $|L|-\mu_{L}\geq 2a$ in $G$ . Let $G_{1}$ and $G_{2}$ be graphs induced by red edges and blue edges, respectively. If $G_{2}$ does not contain $3$ -linear forest, then $\Delta(G_{2})\leq 1$ . We can choose a vertex $u$ of $G_{1}$ and $S\subseteq V(G)-N_{G}[u]$ such that $|S|=n$ . Since $\delta(G_{1}[S])\geq n-2>n/2$ , $G_{1}[S]$ contains a $P_{n}$ . Hence $G$ has a $\widehat{K}_{n}$ with center $u$ , a contradiction. Therefore, $E(L)\neq\emptyset$ . We choose a $3$ -linear forest $L$ from $G_{2}$ such that $e(L)=|L|-\mu_{L}$ is maximum. Subjects to above, suppose that $|L|$ is maximum.

Let $U=V(G)-V(L)$ . Then the following result holds.

Claim 1.

For each component $D$ of $L$ (say, $D=P_{m}$ ), the following results hold.

$(i)$ If $m\geq 6$ , then $E_{G}[V(D),U]\subseteq E(G_{1})$ .
$(ii)$ If $3\leq m\leq 5$ , then either $E_{G}[U,V(D)]\subseteq E(G_{1})$ or there is a vertex $v$ of $D$ such that $E_{G}[U,V(D)-v]\subseteq E(G_{1})$ . Moveover, if $v$ exists, then $v$ is a center vertex of $D$ and $G_{1}[V(D)-\{v\}]$ contains a Hamiltonian path.

Proof.

Suppose that $D=v_{1}v_{2}\ldots v_{m}$ . We first prove the following result.

Fact 1.

For each $u\in U$ and $i\in[m-1]$ , $v_{1}u,v_{m}u\not\in E(G_{2})$ and at most one of $uv_{i},uv_{i+1}$ belongs to $G_{2}$ .

Proof.

If $v_{1}u\in E(G_{2})$ or $v_{m}u\in E(G_{2})$ , then we can find a $3$ -linear forest $L\cup\{v_{1}u\}$ or $L\cup\{v_{m}u\}$ which is larger than $L$ , a contradiction. For $i\in[m-1]$ , if $uv_{i},uv_{i+1}\in E(G_{2})$ , then we can get a larger $3$ -linear forest $(L\setminus v_{i}v_{i+1})\cup\{uv_{i},uv_{i+1}\}$ in $G_{2}$ , a contradiction. ∎

$(i)$ Suppose to the contrary that there exists some $i\in[2,m-1]$ and $u\in U$ such that $v_{i}u\in E(G_{2})$ . Without loss of generality, suppose that $2\leq i\leq m/2$ . Then $(D\backslash\{v_{i}v_{i+1}\})\cup\{v_{i}u\}$ is a new $3$ -linear forests of $G_{2}$ with $e(L^{\prime})=e(L)$ and $|L^{\prime}|=|L|+1$ , which contradicts the choose of $L$ .

$(ii)$ If $E_{G}[U,V(D)]\subseteq E(G_{1})$ , then the result holds. Thus, suppose that there exists a vertex $v_{i}\in V(D)$ and a vertex $u^{\prime}\in U$ such that $v_{i}u^{\prime}\in E(G_{2})$ .

If $m=3$ , then by Fact 1, $i=2$ and $v_{2}$ is the unique vertex such that $E_{G}[V(D)-v_{2},U]\subseteq E(G_{1})$ . Moreover, we have $v_{1}v_{3}\not\in E(G_{2})$ ; otherwise $u^{\prime}v_{2}v_{1}v_{3}$ is a path of $G_{2}$ and we can find a $3$ -linear forest $(L-D)\cup u^{\prime}v_{2}v_{1}v_{3}$ larger than $L$ , a contradiction. Thus, $v_{1}v_{2}$ is a Hamiltonian path of $G_{1}[V(D-v_{2})]$ .

If $m=4$ , then by Fact 1, $i\in\{2,3\}$ . Without loss of generality, assume that $i=2$ . If there is a vertex $z$ of $U$ with $v_{3}z\in E(G_{2})$ , then $z\neq u^{\prime}$ by Fact 1. Hence, $E_{G}[V(D)-v_{2},U]\subseteq E(G_{1})$ . By the same discussion as above, we get that $v_{1}v_{4},v_{1}v_{3}\in E(G_{1})$ ; otherwise there is a $3$ -linear forest larger than $L$ , a contradiction. So, $v_{3}v_{1}v_{4}$ is a Hamiltonian path of $G_{1}[V(D-v_{2})]$ .

If $m=5$ , then $i\notin\{2,4\}$ . Otherwise, either $L^{\prime}=(L\backslash\{v_{2}v_{3}\})\cup\{v_{2}u^{\prime}\}$ or $L^{\prime}=(L\backslash\{v_{4}v_{3}\})\cup\{v_{4}u^{\prime}\}$ is a $3$ -linear forest with $e(L)=e(L^{\prime})$ and $|L|<|L^{\prime}|$ , a contradiction. Hence, $i=3$ and $E_{G}[V(D)-v_{3},U]\subseteq E(G_{1})$ . It is obvious that $v_{1}v_{5},v_{2}v_{5},v_{1}v_{4}\in E(G_{1})$ ; otherwise, we can find a larger $3$ -linear forest than $L$ , a contradiction. Therefore, $v_{4}v_{1}v_{5}v_{2}$ is a Hamiltonian path of $G_{1}[V(D-v_{3})]$ . ∎

We call the unique vertex $v$ in Claim 1 the removable vertex of $D$ . Note that our aim is to prove that $|L|-\mu_{L}\geq 2a$ . For convenience, the proof is proceeded by contradiction, that is, $|L|-\mu_{L}\leq 2a-1$ . In the following proof, in order to get a contradiction, we need to find a red $\widehat{K}_{n}$ .

If $U=\emptyset$ , then $|L|=N$ and $|L|-\mu_{L}\geq\frac{2|L|}{3}=\frac{2N}{3}$ . Since $a\leq\frac{n}{4}$ , it follows that $|L|-\mu_{L}\geq 2a$ , the result follows. Thus, suppose that $U\neq\emptyset$ . Choose a vertex $u_{0}\in U$ such that $|N_{G_{2}}(u_{0},U)|$ is as small as possible. By the maximality of $L$ , we have that $\Delta(G_{2}[U])\leq 1$ , and hence $|N_{G_{2}}(u_{0},U)|\leq 1$ . Moreover, if $|N_{G_{2}}(u_{0},U)|=1$ , then $G_{2}[U]$ is a perfect matching of $G[U]$ . Let $U^{\prime}=U-u_{0}-N_{G_{2}}(u_{0},U)$ . Then $|U^{\prime}|\geq|U|-2$ .

In order to get a contradiction, we need to find a red $\widehat{K}_{n}$ with center $u_{0}$ , that is, to find a path $P_{n}$ in $G_{1}[N_{G_{1}}(u_{0})]$ .

Let $\mathcal{D}_{1}$ be the set of components $D$ of $L$ such that $E_{G}[V(D),U]\subseteq E(G_{1})$ , and let $\mathcal{D}_{2}$ be the set of other components of $L$ . By Claim 1, for each $D\in\mathcal{D}_{2}$ , we have $3\leq|D|\leq 5$ .

The following claim is immediate, which will be used later.

Claim 2.

If $|N_{G_{2}}(u_{0},U)|=1$ , then there is no $P_{3}$ in $\mathcal{D}_{2}$ .

Proof.

Assume, to the contrary, that $\mathcal{D}_{2}$ contains a path $P=v^{\prime}vv^{\prime\prime}$ . Then there exists a vertex $u\in U$ such that $uv\in E(G_{2})$ . Recall that $|N_{G_{2}}(u_{0},U)|=1$ implying $G_{2}[U]$ is a perfect matching of $G[U]$ . Thus, there exists a vertex $u^{\prime}\in U$ such that $uu^{\prime}\in E(G_{2})$ . Let $L^{\prime}$ be a $3$ -linear forest obtained from $L$ by deleting $P$ and then adding $v^{\prime}vuu^{\prime}$ . Then $L^{\prime}$ is a $3$ -linear forest larger than $L$ , a contradiction. ∎

From Claim 2, if $|N_{G_{2}}(u_{0},U)|=1$ , then for each $D\in\mathcal{D}_{2}$ , $|D|\geq 4$ .

Let $A=\bigcup_{D\in\mathcal{D}_{1}}V(D)$ and $B=\bigcup_{D\in\mathcal{D}_{2}}V(D)$ . Let $B_{0}$ be the set of removable vertices. Then by Claim 1,

N_{G_{1}}(u_{0})=A\cup(B-B_{0})\cup U^{\prime}=V(G)-B_{0}-N_{G_{2}}(u_{0},U)-u_{0}.

Since $2a-1\geq|L|-\mu_{L}\geq\frac{2|L|}{3}$ , it follows that

|L|\leq 3a-2,

and hence

|U^{\prime}|\geq N-|L|-2\geq N-3a=n-2a\geq\frac{n}{2}.

Since $N_{G_{1}}(u_{0})=V(G)-B_{0}-N_{G_{2}}(u_{0},U)-u_{0}$ , it suffices to find a path $P_{n}$ in $G_{1}[V(G)-B_{0}-N_{G_{2}}(u_{0},U)-u_{0}]$ obtained from two vertex disjoint paths $J,J^{\prime}$ , which will be defined below, by adding some edges to connect them.

We first construct $J$ . Let $|\mathcal{D}_{2}|=t$ and $L_{1},\ldots,L_{t}$ be all the paths in $\mathcal{D}_{2}$ . Then

t\leq\frac{|L|}{3}\leq a-1<|U^{\prime}|.

Let $f_{i}$ be the removable vertex of $L_{i}$ . By Claim 1, each $G_{1}[V(L_{i})]$ contains a path $L^{\prime}_{i}$ such that $V(L^{\prime}_{i})=V(L_{i})-f_{i}$ . Then $V(L^{\prime}_{i})\subseteq N_{G_{1}}(u_{0})$ for each $i\in[t]$ and $\bigcup_{i\in[t]}V(L^{\prime}_{i})=B-B_{0}$ . Let $z_{i}^{1},z_{i}^{2}$ be the endpoints of $L^{\prime}_{i}$ . Since $t<|U^{\prime}|$ , we can choose a subset $Y=\{y_{1},y_{2},\ldots,y_{t}\}$ of $U^{\prime}$ . Let

E^{\prime}=\{y_{1}z_{1}^{1},y_{2}z_{1}^{2},y_{2}z_{2}^{1},y_{3}z_{2}^{2},\ldots,y_{t}z_{t-1}^{2},y_{t}z_{t}^{1}\}.

Then $E^{\prime}\subseteq E(G_{1})$ and $J=E^{\prime}\cup(\bigcup_{i\in[t]}L^{\prime}_{i})$ is a path of $G_{1}$ with endpoints $y_{1}$ and $z^{2}_{t}$ . It is worth noting that if $\mathcal{D}_{2}=\emptyset$ , then let $J$ be the empty graph.

Now we construct $J^{\prime}$ . Let $X=U^{\prime}-Y$ and $\ell=\min\{|X|,|A|\}$ . It follows from $|U^{\prime}|>|Y|$ that $X\neq\emptyset$ . Let $A^{\prime}$ be a subset of $A$ and $X^{\prime}$ be a subset of $X$ such that $|A^{\prime}|=|X^{\prime}|=\ell$ . It is obvious that $G_{1}[A^{\prime}\cup X^{\prime}]$ contains a red path $J^{\prime}$ of order $2\ell$ . Moreover, one endpoint of $J^{\prime}$ is in $A^{\prime}$ (say $b^{\prime}$ ) and the other endpoint is in $X$ (say $b$ ). Since $X\neq\emptyset$ , if $\ell=0$ , then $A=\emptyset$ , and let $J^{\prime}$ be the empty graph.

We construct a red path $P$ as follows. If both $J,J^{\prime}$ are not empty, then we let $P=J\cup J^{\prime}\cup\{b^{\prime}y_{1}\}$ ; if $J^{\prime}$ is the empty graph, then let $P=J$ ; if $J$ is the empty graph, then let $P=J^{\prime}$ . It is clear that $P$ is a red path of $G_{1}$ with order $2\ell+|B-B_{0}|+t$ and $V(P)\subseteq N_{G_{1}}(u_{0})$ . If $|X|\leq|A|$ , then $\ell=|X|$ and

2\ell+|B-B_{0}|+t=2|U^{\prime}|-t+|B-B_{0}|\geq 2|U^{\prime}|+t\geq n

(note that $|B-B_{0}|\geq 2t$ since $L$ is a $3$ -linear forest). Thus, $u_{0}\vee P$ contains a red $\widehat{K}_{n}$ , a contradiction. Hence, we assume that $|X|>|A|$ below (then $\ell=|A|$ ).

Refer to caption — Figure 1: The path $P^{*}$ .

Claim 3.

$G_{1}[N_{G_{1}}(u_{0})]$ contains a path of order $N-|B_{0}|-1-|N_{G_{2}}(u_{0},U)|$ .

Proof.

Let $U^{\prime\prime}=U^{\prime}-Y-X^{\prime}=X-X^{\prime}$ . Since $X^{\prime}\subseteq X$ and $|X^{\prime}|=\ell=|A|<|X|$ , it follows that $U^{\prime\prime}\neq\emptyset$ . Let $P^{\prime}$ be a maximum path in $G_{1}[U^{\prime\prime}]$ . Since $\Delta(G_{2}[U^{\prime\prime}])\leq 1$ , it follows that $P^{\prime}$ is a Hamiltonian path of $G_{1}[U^{\prime\prime}]$ (say the endpoints of $P^{\prime}$ are $z,z^{*}$ ; if $|U^{\prime\prime}|=1$ , then $z=z^{*}$ ), unless $|U^{\prime\prime}|=2$ and the two vertices of $U^{\prime\prime}$ forms a blue edge.

If $P^{\prime}$ is a Hamiltonian path of $G_{1}[U^{\prime\prime}]$ , then $P^{*}=P^{\prime}\cup P\cup\{z^{2}_{t}z\}$ is a path of $G_{1}$ and $|P^{*}|=N-|B_{0}|-1-|N_{G_{2}}(u_{0},U)|$ . Otherwise, $|U^{\prime\prime}|=2$ (say $U^{\prime\prime}=\{s_{1},s_{2}\}$ ) and $s_{1}s_{2}\in E(G_{2})$ . Thus, we assume that $|P^{\prime}|=|U^{\prime\prime}|-1$ . Then $U^{\prime\prime}=\{s_{1},s_{2}\}$ . Note that one endpoint of $P$ is $z_{t}^{2}$ and the other endpoint is $w\in\{b,y_{1}\}$ (if $J^{\prime}$ is the empty graph, then $w=y_{1}$ ; otherwise $w=b$ ). Since $\Delta(G_{2}[U])\leq 1$ , we have that one of $ws_{1},ws_{2}$ is in $E(G_{1})$ (by symmetry, suppose $ws_{2}\in E(G_{1})$ ). If $J$ is not the empty graph, then $P^{*}=P\cup\{ws_{2},z_{t}^{2}s_{1}\}$ is a path of $G_{1}$ , and $|P^{*}|=N-|B_{0}|-1-|N_{G_{2}}(u_{0},U)|$ ; if $J$ is the empty graph, then $P^{*}=P\cup\{ws_{2},b^{\prime}s_{1}\}$ is a path of $G_{1}$ , and $|P^{*}|=N-|B_{0}|-1-|N_{G_{2}}(u_{0},U)|$ . ∎

By Claim 3, in order to get a $P_{n}$ in $G_{1}[N_{G_{1}}(u_{0})]$ , we only need to prove that

N-|B_{0}|-1-|N_{G_{2}}(u_{0},U)|\geq n.

Suppose, to the contrary, that $N-|B_{0}|-1-|N_{G_{2}}(u_{0},U)|<n$ . Then

n+a=N\leq n+|B_{0}|+|N_{G_{2}}(u_{0},U)|,

and hence $a\leq|B_{0}|+|N_{G_{2}}(u_{0},U)|$ . If $|N_{G_{2}}(u_{0},U)|=0$ , then $a\leq|B_{0}|$ . Recall that $|L|\leq 3a-2$ . Then $a\leq|B_{0}|\leq\mu_{L}\leq\frac{3a-2}{3}$ , a contradiction. If $|N_{G_{2}}(u_{0},U)|=1$ , then it follows from Claim 2 that each path of $\mathcal{D}_{2}$ has order at least $4$ , and hence $|B_{0}|\leq\frac{|L|}{4}$ . Then $a\leq|B_{0}|+1\leq\frac{|L|}{4}+1\leq\frac{3a+2}{4}$ , which contradicts that $a\geq 3$ . Therefore, we get a $P_{n}$ in $N_{G_{1}}(u_{0})$ , and hence there is a $\widehat{K}_{n}$ in $G_{1}$ , a contradiction. ∎

Now we give the proof of Theorem 1.6.

Proof of Theorem 1.6: Let $N=n+\lceil m/2\rceil-1$ and $G=K_{N}$ . We partition $V(G)$ into two parts $A,B$ such that $|A|=n$ and $|B|=\lceil m/2\rceil-1$ . Let $\Gamma$ be a red/blue edge-coloring of $G$ such that each edge of $G[A]$ is red and the other edges are blue. It is easy to verify that there is no a red copy of $\widehat{K}_{n}$ . Suppose that $L$ is a blue linear forest with maximum number of edges. Since each edge of $L$ incidents to at least one vertex of $B$ and each vertex of $B$ incidents to at most two edges of $L$ , it follows that $e(L)\leq 2|B|\leq m-1$ , and hence $G$ does not contain blue linear forests of size at least $m$ . Therefore, $r(\widehat{K}_{n},\mathcal{L})\geq n+\lceil\frac{m}{2}\rceil$ and $r(\widehat{K}_{n},\mathcal{L}^{\prime})\geq n+\lceil\frac{m}{2}\rceil$ . By Lemmas 3.1 and 3.2, we have $r(\widehat{K}_{n},\mathcal{L})\leq n+\lceil\frac{m}{2}\rceil$ and $r(\widehat{K}_{n},\mathcal{L}^{\prime})\leq n+\lceil\frac{m}{2}\rceil$ by assuming that $a=\lceil\frac{m}{2}\rceil$ . Hence, $r(\widehat{K}_{n},\mathcal{L})=n+\lceil\frac{m}{2}\rceil$ .

4 Proof of Theorems 1.7, 1.8 and 1.9

In order to prove Theorems 1.7, 1.8 and 1.9, we need the exact values of $b_{k}(P_{n})$ and $t(P_{n})$ first. The following is the exact value of $b_{k}(P_{n})$ .

Lemma 4.1.

If $k\geq 3$ and $n\geq 2(k-1)$ , then

b_{k}(P_{n})=\left\{\begin{array}[]{ll}n,&\mbox{if}~{}2(k-1)\leq n\leq 4(k-2)+1,\\ \left\lceil\frac{3n-3}{2}\right\rceil,&\mbox{if}~{}n>4(k-2)+1.\\ \end{array}\right.

Proof.

Let $N$ be a positive integer and $G$ be an edge-colored $K_{N}$ such that the edge-coloring belongs to $\mathcal{B}_{k}(N)$ . Let $V_{1},\ldots,V_{k-1}$ be all the $k-1$ parts. Without loss of generality, let $2\leq|V_{1}|\leq\ldots\leq|V_{k-1}|$ . Let $U=\bigcup_{i=1}^{k-2}V_{i}$ .

If $2(k-1)\leq n\leq 4(k-2)+1$ , then let $N=n$ . It is obvious that $|U|\geq 2(k-2)\geq\left\lfloor\frac{n}{2}\right\rfloor$ . By Lemma 2.1, $G$ contains a Hamiltonian path with color 1. Thus, $b_{k}(P_{n})=n$ . Therefore, let $n>4(k-2)+1$ in the following discussion.

We first prove the upper bounds. Let $N=\left\lceil\frac{3n-3}{2}\right\rceil$ . If $|U|\geq\left\lfloor\frac{n}{2}\right\rfloor$ , then by Lemma 2.1, $G$ contains a monochromatic path $P_{n}$ with color $1$ . If $|U|<\left\lfloor\frac{n}{2}\right\rfloor$ , then

\displaystyle|V_{k-1}|\geq N-(\left\lfloor\frac{n}{2}\right\rfloor-1)=n.

(1)

Thus, by Theorem 2.1, there is an integer $m\geq 2$ such that $|V_{k-1}|=r(P_{n},P_{m})$ , and hence $G[V_{k-1}]$ contains either a monochromatic $P_{m}$ with color $1$ or a monochromatic $P_{n}$ with color $k$ . If the latter holds, then the monochromatic $P_{n}$ is obtained. Hence, suppose that the former holds. If $m\geq n$ , then the result follows. Thus, let $m<n$ and $G[V_{i-1}]$ contains a monochromatic $P_{m}$ with color $1$ . Then $|V_{k-1}|=r(P_{n},P_{m})=n+\left\lfloor\frac{m}{2}\right\rfloor-1$ . Since $U\neq\emptyset$ and $V_{k-1}-V(P_{m})\neq\emptyset$ , it follows that $G$ contains a monochromatic $P_{m+2}$ that is obtained from the $P_{m}$ by adding two edges $e_{1},e_{2}$ between $U$ and $V_{k-1}-V(P_{n})$ , where $e_{1}$ joins one endpoint of $P_{m}$ and a vertex of $U$ (say $x$ is the endpoint of $e_{1}$ belonging to $U$ ), and $e_{2}$ joins $x$ and a vertex of $V_{k-1}-V(P_{m})$ . This implies that $G$ contains a monochromatic $P_{n}$ when $n-2\leq m<n$ . Hence, we assume that $n-3\geq m\geq 2$ below.

Case 1.

$m$ is odd.

Let $W=V_{k-1}-V(P_{m})$ . If $|W|\leq|U|$ , then $G[W\cup U]$ contains a monochromatic path $P_{2|W|}$ with color $1$ , and hence $G$ contains a monochromatic $P_{m+2|W|}$ obtained form the monochromatic paths $P_{m}$ and $P_{2|W|}$ by adding an edge joins one endpoint of $P_{m}$ and the endpoint of $P_{2|W|}$ belonging to $U$ . Since $m+2|W|=|V_{k-1}|+|W|\geq n$ , $G$ contains a monochromatic $P_{n}$ . If $|W|>|U|$ , then $G$ contains a monochromatic copy of $P_{2|U|+m}$ . It suffices to prove that $2|U|+m\geq n$ . Since $m$ is odd, it follows that $|V_{k-1}|=n+\frac{m-1}{2}-1$ , and hence $m=2|V_{k-1}|-2n+3$ . So

\displaystyle 2|U|+m=2|U|+2|V_{k-1}|-2n+3=2N-2n+3=n.

Case 2.

$m$ is even and $m\geq 4$ .

Let $m+2=m_{1}+m_{2}$ , where $m_{1},m_{2}\geq 3$ and $m_{1},m_{2}$ are odd. Since $|V_{k-1}|=n+\frac{m}{2}-1=n+\frac{(m+2)-2}{2}-1$ and $n-3\geq m$ , it follows from Theorem 2.2 that $|V_{k-1}|=r(P_{n},P_{m_{1}}\cup P_{m_{2}})$ , and hence $G[V_{k-1}]$ contains either a monochromatic path $P_{n}$ with color $k$ , or a monochromatic path $P_{m_{1}}\cup P_{m_{2}}$ with color $1$ . If the former holds, then $G$ contains a monochromatic $P_{n}$ . Hence, suppose that the latter holds. Assume that $u\in U$ . Let $U^{\prime}=U-\{u\}$ and $W=V_{k-1}-V(P_{m_{1}}\cup P_{m_{2}})$ . If $|W|\leq|U^{\prime}|$ , then $G[W\cup U^{\prime}]$ contains a monochromatic path $P_{2|W|}$ with color $1$ . We can choose the two endpoints of $P_{2|W|}$ as $x\in W$ and $y\in U^{\prime}$ . Without loss of generality, suppose that the two endpoints of $P_{m_{1}}$ are $x_{1}^{\prime},y_{1}^{\prime}$ and the two endpoints of $P_{m_{2}}$ are $x_{2}^{\prime},y_{2}^{\prime}$ . Then $P_{m_{1}}\cup P_{m_{2}}\cup P_{2|W|}\cup\{uy_{1}^{\prime},ux_{2}^{\prime},y_{2}^{\prime}y\}$ is a monochromatic $P_{2|W|+(m_{1}+m_{2})+1}$ with color $1$ . Note that

2|W|+(m_{1}+m_{2})+1=|W|+|V_{k-1}|+1>|V_{k-1}|\geq n

by the inequality (1). It follows that $G$ contains a monochromatic copy of $P_{n}$ with color $1$ . If $|W|>|U^{\prime}|$ , then $G$ contains a monochromatic copy of $P_{m_{1}+m_{2}+1+2|U^{\prime}|}$ . We need to prove that $m_{1}+m_{2}+1+2|U^{\prime}|=m+2|U|+1\geq n$ . Since $|V_{k-1}|=n+\left\lfloor\frac{m}{2}\right\rfloor-1$ and $m$ is even, it follows that $m=2|V_{k-1}|-2n+2$ , and hence

m+2|U|+1=2|V_{k-1}|-2n+2|U|+3=2(N-n)+3\geq n.

Case 3.

$m$ is even and $2\leq m\leq 3$ .

In this case, $|V_{k-1}|=n$ and $|U|=N-|V_{k-1}|=\lceil\frac{n-1}{2}\rceil-1$ . Since $|V_{k-1}|=r(P_{n},P_{3})$ , if $G[V_{k-1}]$ does not contain a monochromatic copy of $P_{n}$ with color $k$ , the monochromatic $P_{n}$ is obtained. Otherwise, $G[V_{k-1}]$ contain monochromatic $F=P_{3}$ with color $1$ . We can choose a subset $W$ of $V_{k-1}-V(F)$ such that $|W|=\lceil\frac{n-1}{2}\rceil-1$ , since $|V_{k-1}-V(F)|=n-3\geq\lceil\frac{n-1}{2}\rceil-1$ . Then $G[W\cup U]$ contains a monochromatic $P_{2|W|}$ with color $1$ , and there is a monochromatic $P_{2|W|+3}$ with color $1$ that is obtained by connecting the endpoint of $P_{2|W|}$ belonging to $U$ and an endpoint of $P_{3}$ . Since $2|W|+3\geq n$ , there is a monochromatic $P_{n}$ with color $1$ .

Now we prove the lower bounds. Let $M=\left\lceil\frac{3n-3}{2}\right\rceil-1$ and $G=K_{M}$ . We partition $V(G)$ into $k-1$ parts $V_{1},\ldots,V_{k-1}$ such that $|V_{1}|=|V_{2}|=\ldots=|V_{k-2}|=2$ and $|V_{k-1}|=\left\lceil\frac{3n-1}{2}-2(k-1)\right\rceil$ . Let $V_{i}=\{u_{i},v_{i}\}$ for $i\in[k-2]$ , and let $G[V_{k-1}]=H\cup\overline{H}$ , where $H$ is the disjoint union of $H_{1}=K_{\left\lceil\frac{n-4(k-1)+1}{2}\right\rceil}$ and $H_{2}=K_{n-1}$ . Choose a $k$ -edge-coloring $\Gamma\in\mathcal{B}_{k}(M)$ such that $u_{i}v_{i}$ is colored by $i+1$ for $i\in[k-2]$ and $H$ is a monochromatic graph with color $k$ , and the other edges are colored by $1$ . It is easy to verify that there is no monochromatic $P_{n}$ with color $i\geq 2$ . For color $1$ , it is clear that the edges with color $1$ induces a spanning complete $k$ -partite graph with $k$ parts $V_{1},V_{2},\ldots,V_{k-2},V(H_{1}),V(H_{2})$ . Let $P$ be a minimum monochromatic path. Since $V(H_{2})$ is an independent set in the complete $k$ -partite graph, each edge of $P$ incidents with a vertex of $V(G)-V(H_{2})$ , and hence $e(P)\leq 2|V(G)-V(H_{2})|=2(M-n+1)\leq n-2.$ Thus, $|P|\leq n-1$ , and there is no monochromatic $P_{n}$ with color $1$ . Therefore, there is no monochromatic $P_{n}$ in $G$ , which implies that $b_{k}(P_{n})\geq M+1=\left\lceil\frac{3n-3}{2}\right\rceil$ . ∎

The following is the exact value of $t(P_{n})$ .

Lemma 4.2.

If $n\geq 3$ , then

t(P_{n})=\left\{\begin{array}[]{ll}\frac{3n}{2}-1,&n\mbox{ is even},\\ \frac{3n-1}{2},&n\mbox{ is odd }.\end{array}\right.

Proof.

We first prove the lower bounds. Suppose that $M=\frac{3n}{2}-2$ if $n$ is even, and $M=\frac{3n-1}{2}-1$ if $n$ is odd. Let $\Gamma^{\prime}\in\mathcal{T}(M)$ be an edge-coloring of $G^{\prime}=K_{M}$ and the three parts are $V_{1},V_{2},V_{3}$ . If $n$ is even, then let $|V_{1}|=\frac{n}{2}$ and $|V_{2}|=|V_{3}|=\frac{n}{2}-1$ . If $n$ is odd, then let $|V_{1}|=|V_{2}|=|V_{3}|=\frac{n-1}{2}$ . Moreover, let $G^{\prime}[V_{i}]$ be a complete graph with color $i$ . Then $K_{M}$ does not contain a monochromatic copy of $P_{n}$ . Therefore, the lower bounds are obtained.

Now we prove the upper bounds. Suppose that $N=\frac{3n}{2}-1$ if $n$ is even, and $N=\frac{3n-1}{2}$ if $n$ is odd. Let $\Gamma\in\mathcal{T}(N)$ be an edge-coloring of $K_{N}$ with the three parts $V_{1},V_{2},V_{3}$ . Without loss of generality, suppose that $|V_{1}|\geq|V_{2}|\geq|V_{3}|$ . Note that $V_{2},V_{3}\neq\emptyset$ .

Let $a_{1}=n-2|V_{2}|$ . If $a_{1}<2$ , then $|V_{2}|\geq\lceil\frac{n-1}{2}\rceil$ . If $|V_{1}\cup V_{2}|\geq n$ , then there is a monochromatic $P_{n}$ between $V_{1}$ and $V_{2}$ . Otherwise, suppose that $|V_{1}\cup V_{2}|\leq n-1$ . Then $|V_{1}|\leq\lfloor\frac{n-1}{2}\rfloor$ . Since $|V_{1}|\geq|V_{2}|\geq|V_{3}|$ , it follows that $n$ is odd and $|V_{1}|=|V_{2}|=\frac{n-1}{2}$ . However, $|V_{3}|=N-|V_{1}\cup V_{2}|\geq(3n-1)/2-(n-1)=(n+1)/2>|V_{2}|$ , a contradiction. Therefore, suppose $a_{1}\geq 2$ below.

Let $a_{2}=|V_{1}|-\lfloor\frac{a_{1}}{2}\rfloor+1$ . Then $a_{2}\geq a_{1}$ . Otherwise, if $a_{2}<a_{1}$ , then

	$\displaystyle\|V_{1}\|$	$\displaystyle=a_{2}+\left\lfloor\frac{a_{1}}{2}\right\rfloor-1\leq a_{1}+\left\lfloor\frac{a_{2}}{2}\right\rfloor-1\leq a_{1}+\left\lfloor\frac{a_{1}-1}{2}\right\rfloor-1$
		$\displaystyle\leq n-2\|V_{2}\|+\left\lfloor\frac{n-2\|V_{2}\|-1}{2}\right\rfloor-1=n-3\|V_{2}\|+\left\lfloor\frac{n-3}{2}\right\rfloor$
		$\displaystyle\leq n-(N-\|V_{1}\|)-\|V_{2}\|+\left\lfloor\frac{n-3}{2}\right\rfloor$
		$\displaystyle\leq\|V_{1}\|-\|V_{2}\|<\|V_{1}\|,$

a contradiction. Thus, $2\leq a_{1}\leq a_{2}$ . By Theorem 2.1, we have that $|V_{1}|=r(P_{a_{1}},P_{a_{2}})$ . Hence, $G[V_{1}]$ contains either a monochromatic copy of $P_{a_{1}}$ with color $1$ or a monochromatic copy of $P_{a_{2}}$ with color $3$ .

Suppose that $G[V_{1}]$ contains a monochromatic copy of $P_{a_{1}}$ with color $1$ (say $w$ is an endpoint of $P_{a_{1}}$ ). Let $U_{1}=V_{1}-V(P_{a_{1}})$ and let $\ell=\min\{|U_{1}|,|V_{2}|\}$ . Then there is a monochromatic $P_{2\ell}$ between $U_{1}$ and $V_{2}$ with color $1$ . Without loss of generality, suppose that $w_{1}$ are endpoints of the path $P_{2\ell}$ with $w_{1}\in V_{2}$ . Then $P_{2\ell}\cup P_{a_{1}}\cup\{ww_{1}\}$ monochromatic path of order $2\ell+a_{1}$ (see Figure 2 (1)). We only need to verify that $2\ell+a_{1}\geq n$ below. If $|U_{1}|\geq|V_{2}|$ , then $2\ell+a_{1}=2|V_{2}|+a_{1}=n$ . If $|U_{1}|<|V_{2}|$ , then

2\ell+a_{1}=2|U_{1}|+a_{1}=2|V_{1}|-a_{1}=2(|V_{1}|+|V_{2}|)-n\geq 2\left\lceil\frac{2N}{3}\right\rceil-n=n.

Suppose that $G[V_{1}]$ contains a monochromatic $P_{a_{2}}$ with color $3$ . Let $a^{\prime}=\min\{a_{2},|V_{1}|-|V_{3}|\}$ . Then we can choose a subpath $P$ of $P_{a_{2}}$ with $|P|=a^{\prime}$ (say $w$ is an endpoint of $P$ ). Let $U_{1}=V_{1}-V(P)$ . Then $|U_{1}|\geq|V_{3}|$ . Then there is a monochromatic $P_{2|V_{3}|}$ between $U_{1}$ and $V_{3}$ with color $3$ . Without loss of generality, suppose that $w_{1}$ is the endpoint of the path $P_{2|V_{3}|}$ with $w_{1}\in V_{3}$ . Then $P_{2|V_{3}|}\cup P_{a_{2}}\cup\{ww_{1}\}$ monochromatic path of order $2|V_{3}|+a^{\prime}$ (see Figure 2 (2)). We only need to verify that $2|V_{3}|+a^{\prime}\geq n$ below. Note that

\displaystyle a_{2}=|V_{1}|-\left\lfloor\frac{a_{1}}{2}\right\rfloor+1=|V_{1}|-\left\lfloor\frac{n}{2}\right\rfloor+|V_{2}|+1=(N-|V_{3}|)-\left\lfloor\frac{n}{2}\right\rfloor+1\geq n-|V_{3}|.

If $a^{\prime}=a_{2}$ , then $2|V_{3}|+a^{\prime}=2|V_{3}|+a_{2}\geq n$ . If $a^{\prime}=|V_{1}|-|V_{3}|$ , then $2|V_{3}|+a^{\prime}=|V_{1}|+|V_{3}|\geq a_{2}+|V_{3}|\geq n$ . ∎

Proof of Theorem 1.7: Let $\Gamma$ be an edge-coloring of $K_{N}$ such that $K_{N}$ does not contain rainbow $P_{5}$ . From Theorem 1.3, one of $(i),(ii)$ holds if $k\geq 4$ , and one of $(iii)-(v)$ holds if $k=4$ . Note that if $N\geq 6$ , then $K_{N}$ contains a monochromatic $P_{N-1}$ with color $1$ whenever one of $(ii)-(v)$ holds.

For $2(k-1)\leq n\leq 4(k-2)+1$ , let $N=n+1$ . Since $N\geq 6$ , $K_{N}$ contains a monochromatic $P_{n}$ with color $1$ whenever one of $(ii)-(v)$ holds. By Lemma 4.1, $b_{k}(P_{n})=n$ . So, $\operatorname{gr}_{k}(P_{5}:P_{n})\leq n+1$ . Since we can choose a $\Gamma$ of $(ii)$ such that $K_{n}$ does not contain monochromatic $P_{n}$ , $\operatorname{gr}_{k}(P_{5}:P_{n})=n+1$ .

For $n>4(k-2)+1$ , let $N=\lceil\frac{3n-3}{2}\rceil$ . By Lemma 4.1, $b_{k}(P_{n})=N$ . Since $n\geq 10$ , it follows that $N\geq n+1$ , and hence $K_{N}$ contains a monochromatic copy of $P_{n}$ whenever $\Gamma$ satisfies one of $(ii)-(v)$ . Therefore, $\operatorname{gr}_{k}(P_{5}:P_{n})=N=\lceil\frac{3n-3}{2}\rceil$ .

Proof of Theorem 1.8: Let $\Gamma^{\prime}$ be an edge-coloring of $K_{N^{\prime}}$ such that $K_{N^{\prime}}$ does not contain rainbow $P_{4}^{+}$ . By Theorem 1.5, if $k=4$ , then either $\Gamma^{\prime}\in\{G_{2}(N^{\prime}),G_{3}(N^{\prime})\}$ or $(i)$ holds; if $k\geq 5$ , then $(i)$ holds.

Suppose $k\geq 5$ . Then $\operatorname{gr}_{4}(P_{4}^{+}:P_{n})=b_{k}(n)$ . By Lemma 4.1, the result holds. Thus, we talk about the case $k=4$ below. If $n\geq 6$ , then the maximum monochromatic path in $K_{N^{\prime}}$ is $P_{N^{\prime}-2}$ when $\Gamma^{\prime}=G_{2}(N^{\prime})$ , and is $P_{N^{\prime}}$ when $\Gamma^{\prime}=G_{3}(N^{\prime})$ . Thus, $\operatorname{gr}_{4}(P_{4}^{+}:P_{n})\geq n+2$ when $n\geq 6$ . If $2(k-1)\leq n\leq 4(k-2)+1$ , then $b_{k}(n)=n$ , and hence $\operatorname{gr}_{4}(P_{4}^{+}:P_{n})=n+2$ . If $n>4(k-2)+1=9$ , then $b_{k}(P_{n})=\lceil\frac{3n-3}{2}\rceil\geq n+2$ , and hence $\operatorname{gr}_{4}(P_{4}^{+}:P_{n})=\lceil\frac{3n-3}{2}\rceil$ .

Proof of Theorem 1.9: Let $\Gamma^{*}$ be an edge-coloring of $K_{N^{*}}$ such that $K_{N^{*}}$ does not contain rainbow $K_{1,3}$ . If $k=3$ , then either $\Gamma^{*}\in\mathcal{T}(N^{*})$ or $\Gamma^{*}\in\mathcal{B}_{3}(N^{*})$ . Therefore, $\operatorname{gr}_{3}(K_{1,3}:P_{n})=\max\{t(P_{n}),b_{3}(P_{n})\}=t(P_{n})$ . If $k\geq 4$ , then $\Gamma^{*}\in\mathcal{B}_{k}(N^{*})$ and hence $\operatorname{gr}_{k}(K_{1,3}:P_{n})=b_{k}(P_{n})$ .

5 Proof of Theorem 1.10

In order to prove Theorem 1.10, we need the exact values of $b_{3}(\widehat{K}_{n})$ and a upper bound of $t(\widehat{K}_{n})$ . The following is the exactly value of $b_{3}(\widehat{K}_{n})$ .

Lemma 5.1.

If $n\geq 5$ and $n$ is odd, then $b_{3}(\widehat{K}_{n})=\left\lfloor\frac{5n}{2}\right\rfloor$ ; if $n\geq 5$ and $n$ is even, then $\left\lfloor\frac{5n}{2}\right\rfloor-1\leq b_{3}(\widehat{K}_{n})\leq\left\lfloor\frac{5n}{2}\right\rfloor$ .

Proof.

The following claim indicates the lower bounds of $b_{3}(\widehat{K}_{n})$ .

Claim 4.

Let $N^{\prime}=\lfloor(5n)/2\rfloor-1$ if $n$ is odd, and let $N^{\prime}=\lfloor(5n)/2\rfloor-2$ if $n$ is even. There exists an $3$ -edge-coloring $\Gamma\in\mathcal{B}_{3}(n)$ of $G=K_{N^{\prime}}$ such that $G$ does not contain monochromatic $\widehat{K}_{n}$ .

Proof.

We construct $\Gamma$ as follows.

•

Partition $V(G)$ into four parts $A,B_{1},B_{2},B_{3}$ such that $|A|=n$ , $|B_{1}|=|B_{2}|=|B_{3}|=\frac{n-1}{2}$ if $n$ is odd, and $|B_{1}|=\frac{n}{2}$ and $|B_{2}|=|B_{3}|=\frac{n}{2}-1$ if $n$ is even.
•

Let $B=B_{1}\cup B_{2}\cup B_{3}$ . Each edge of $G[A]$ is colored by $3$ , each edge of $E_{G}[A,B]$ is colored by $1$ , each edge between the three parts $B_{1},B_{2},B_{3}$ is colored $2$ , and each edge in $B_{1}$ , $B_{2}$ and $B_{3}$ are colored by $1$ .

Clearly, this edge-coloring $\Gamma$ belongs to $\mathcal{B}_{3}(M)$ and the two parts are $A$ and $B$ . It is easy to verify that there is no monochromatic $\widehat{K}_{n}$ with color $2$ or $3$ . Now we prove that there is no monochromatic $\widehat{K}_{n}$ with color $1$ . Suppose to the contrary that there is a monochromatic $\widehat{K}_{n}=v\vee P$ with color $1$ , where $P$ is a monochromatic $P_{n}$ with color $1$ and $v$ is the center of the $\widehat{K}_{n}$ . Let $G_{1}$ be the subgraph of $G$ induced by all edges with color $1$ . Since $G_{1}[B]$ does not contain monochromatic $P_{n}$ , $v\notin A$ . Thus, $v\in B_{i}$ for some $i\in[3]$ . Then $P$ is a subgraph $G_{1}[(B_{i}-v)\cup A]$ . However, since $G_{1}[(B_{i}-v)\cup A]$ is a complete bipartite graph with two parts $A$ and $B_{i}-v$ , and since $|B_{i}-v|\leq\frac{n-1}{2}-1$ , it follows that the maximum path in $G_{1}[(B_{i}-v)\cup A]$ is $2|B_{i}-v|+1\leq n-2$ , a contradiction. ∎

Now we prove the upper bound. Suppose that $N=\left\lfloor\frac{5n}{2}\right\rfloor$ . Let $G$ be an edge-colored $K_{N}$ and the edge-coloring belong to $\mathcal{B}_{3}(N)$ . Then $V(G)$ can be partitioned into two parts $A,B$ with $2\leq|A|\leq|B|$ such that each edge of $G[A]$ is colored with $1$ or $3$ , each edge of $G[B]$ is colored with $1$ or $2$ , and each edge between $A$ and $B$ is colored with $1$ .

Case 1 $|A|<\frac{n}{2}$ .

In this case, $|B|\geq 2n=r(P_{n},\widehat{K}_{n})$ by Theorem 2.5. Then there is either a monochromatic copy of $P_{n}$ with color $1$ or a monochromatic copy of $\widehat{K}_{n}$ with color $2$ in $G[B]$ , and hence there is either a monochromatic copy of $\widehat{K}_{n}$ with color $2$ , or a monochromatic copy of $\widehat{K}_{n}$ with color $1$ which is obtained form the monochromatic copy of $P_{n}$ with color $1$ and a vertex $v\in A$ by adding all possible edges between $v$ and $V(P_{n})$ .

Case 2 $\lceil\frac{n}{2}\rceil\leq|A|\leq n$ .

Clearly, $|B|\geq\left\lfloor\frac{3n}{2}\right\rfloor\geq r(K_{1,\left\lfloor n/2\right\rfloor},\widehat{K}_{n})$ . Thus, there is either a monochromatic copy of $K_{1,\left\lfloor n/2\right\rfloor}$ with color $1$ or a monochromatic copy of $\widehat{K}_{n}$ with color $2$ in $G[B]$ . If the latter holds, then the result follows. If the former holds, then let $u_{0}$ be the center and $U$ be the set of leaves of the star $K_{1,\left\lfloor n/2\right\rfloor}$ . Since $|U|=\left\lfloor n/2\right\rfloor$ , $|A|\geq\lceil\frac{n}{2}\rceil$ and each edge between $U$ and $A$ is colored by $1$ , it follows that there is a monochromatic path $P=P_{n}$ with color $1$ and $V(P)\subseteq U\cup A$ , and hence $u_{0}\vee P$ is a monochromatic copy of $\widehat{K}_{n}$ with color $1$ .

Case 3 $|A|>n$ .

Clearly, $|B|>n$ also holds. Suppose that there is no monochromatic $\widehat{K}_{n}$ with color $2$ or $3$ . We will show that there is a monochromatic $\widehat{K}_{n}$ with color $1$ below. Let $|A|=n+a$ and $|B|=n+b$ , where $a,b\geq 1$ . Since $a+b=\left\lfloor\frac{n}{2}\right\rfloor$ , it follows that $a,b<\frac{n}{2}$ . Since $|A|\leq|B|$ , we have that $a\leq b$ and $a\leq\left\lfloor\frac{n}{4}\right\rfloor$ . By Theorem 2.7, $|B|\geq r(K_{1,b},\widehat{K}_{n})$ and hence there is a monochromatic copy of $K_{1,b}$ with color $1$ in $G[B]$ . Let $u_{0}$ be the center and let $U$ be the set of leaves in $K_{1,b}$ . Then $|U|=b$ .

By Lemma 3.1 and Lemma 3.2, one of the following statements holds.

•

$a\geq 3$ and there is a $3$ -linear forest $L$ in $G[A]$ with color $1$ such that $|L|-\mu_{L}\geq 2a$ , where $\mu_{L}$ is the number of components of $L$ .
•

$a=1$ and there is either a $2P_{2}$ or a $P_{3}$ in $G[A]$ with color $1$ .
•

$a=2$ and there is either a $P_{2}\cup P_{4}$ (the vertex disjoint union of $P_{2}$ and $P_{4}$ ), or a $P_{5}$ , or a $2P_{3}$ in $G[A]$ with color $1$ .

In above cases, $|L|-\mu_{L}\geq 2a$ . If $a\geq 3$ , then we can choose the $3$ -linear forest $L$ such that $|L|-\mu_{L}=2a+\varepsilon$ , where $0\leq\varepsilon\leq 2$ .

Claim 5.

$|L|\leq 3a+3$ when $a\geq 3$ and $|L|\leq 2a+2$ when $a\in\{1,2\}$ . Moreover, $\mu_{L}\leq|U|+1$ .

Proof.

If $a\geq 3$ , then $L$ is a $3$ -linear forest and hence $\mu_{L}\leq|L|/3$ . Thus, $|L|\leq 3a+3$ . Since $a\leq b$ , it follows that

\mu_{L}\leq\frac{|L|}{3}\leq a+1\leq b+1=|U|+1.

If $a=1$ or $a=2$ , it is easy to verify that $|L|\leq 2a+2$ and $\mu_{L}\leq 2$ . Hence, $\mu_{L}\leq 2\leq|U|+1$ , since $|U|=b\geq 1$ . ∎

By Claim 5, we can choose $\mu_{L}-1$ vertices of $U$ (say $y_{1},\ldots,y_{\mu_{L}-1}$ ). Let $U^{\prime}=U-Y$ , where $Y=\{y_{1},\ldots,y_{\mu_{L}-1}\}$ .

Claim 6.

$|A|-|L|>|U^{\prime}|$ .

Proof.

If $a\geq 3$ , then $|L|\leq 3a+3$ and

\displaystyle|A|-|L|\geq n+a-(3a+3)=n-2a-3\geq n-2\left(\lfloor n/2\rfloor-b\right)-3\geq 2b-3.

Since $b\geq a\geq 3$ , $|A|-|L|\geq b>|U^{\prime}|$ . If $a\in\{1,2\}$ , then $|L|\leq 2a+2$ and

|A|-|L|\geq n+a-(2a+2)=n-a-2=n-\left(\lfloor n/2\rfloor-b\right)-2\geq b>|U^{\prime}|.

∎

By Claim 6, we can choose a subset $A^{\prime}$ of $A-V(L)$ such that $|A^{\prime}|=|U^{\prime}|$ . We assume that $L$ consists of $\mu_{L}$ paths $D_{1},D_{2},\ldots,D_{\mu_{L}}$ , and the two endpoints of $D_{i}$ are $z_{i}^{1}$ and $z_{i}^{2}$ . Observe that we can construct a monochromatic path $P^{\prime}$ that is obtained from $L$ and $Y$ by connecting $y_{i}$ and $z_{i}^{2},z_{i+1}^{1}$ , where $i\in[\mu_{L}-1]$ . On the other hand, since the edges between $U^{\prime}$ and $A^{\prime}$ are colors by $1$ , we can get a monochromatic $P^{\prime\prime}$ of order $2|U^{\prime}|$ with one endpoint in $A^{\prime}$ and the other endpoint in $U^{\prime}$ (say $z$ is the endpoint of $P^{\prime\prime}$ belonging to $U^{\prime}$ ). Then there is a monochromatic path $P$ with color $1$ that is obtained from $P^{\prime}$ and $P^{\prime\prime}$ by adding the edge $zz_{\mu_{L}}^{2}$ . Hence, $u_{0}\vee P$ is monochromatic kipas (see Figure 4). Note that

	$\displaystyle\|P\|$	$\displaystyle=\|L\|+\|Y\|+\|U^{\prime}\|+\|A^{\prime}\|=\|L\|+\|Y\|+2(b-\|Y\|)$
		$\displaystyle=2b+\|L\|-\|Y\|=2b+\|L\|-\mu_{L}+1.$

If $a\geq 3$ , then $|L|-\mu_{L}=2a+\varepsilon$ . Hence, $|P|=2b+2a+\varepsilon+1\geq n$ , and $u_{0}\vee P$ contains a monochromatic $\widehat{K}_{n}$ with color $1$ . If $a\in\{1,2\}$ , it is easy to check that $|L|-\mu_{L}=2a$ . Hence, $|P|=2b+2a+1\geq n$ . ∎

The following is an upper bound of $t(\widehat{K}_{n})$ .

Lemma 5.2.

If $n\geq 5$ , then $t(\widehat{K}_{n})\leq\left\lfloor\frac{5n}{2}\right\rfloor$ if $n$ is odd, and $t(\widehat{K}_{n})\leq\left\lfloor\frac{5n}{2}\right\rfloor-1$ if $n$ is even.

Proof.

Suppose that $N=\left\lfloor\frac{5n}{2}\right\rfloor$ if $n$ is odd, and $N=\left\lfloor\frac{5n}{2}\right\rfloor-1$ if $n$ is even. Let $G=K_{N}$ . Choose an edge-coloring of $\mathcal{T}(G)$ with parts $A,B,C$ . Without loss of generality, let $|A|\geq|B|\geq|C|$ and let $|A|=a,|B|=b$ and $|C|=c$ . Then $a\geq\lceil\frac{5n}{6}\rceil-1$ .

If $|A|\geq\left\lfloor\frac{3n}{2}\right\rfloor$ , then $a\geq r(P_{n},P_{n})$ , and hence there is a monochromatic copy of $P_{n}$ in $G[A]$ colored by $1$ or $3$ . Since $B,C$ are both nonempty sets, it follows that there is a monochromatic copy of $\widehat{K}_{n}$ in $G$ . Thus, suppose that $|A|<\left\lfloor\frac{3n}{2}\right\rfloor$ . Then $b+c\geq n$ and $|B|=b\geq(b+c)/2\geq\frac{n}{2}$ . The proof will be given by contradiction, that is, $G$ does not contain a monochromatic copy of $\widehat{K}_{n}$ . Suppose that $H_{1},H_{2}$ are two subgraphs induced by edges in $G[B]$ and $G[C]$ with color $2$ , respectively. Let $S$ be a star in $H_{2}$ such that $e(S)$ is maximum. Let $u_{0}$ be the center of $S$ . Let $P^{*}$ be a path in $H_{1}$ such that $e(P^{*})$ is maximum. Let $X=V(S)-\{u_{0}\}$ , $|X|=c_{1}$ and $|P^{*}|=b_{1}$ . Then $0\leq c_{1}\leq c-1$ and $1\leq b_{1}\leq b$ .

Claim 7.

$G[B]$ and $G[C]$ contain a monochromatic copies of $K_{1,b-b_{1}}$ and $K_{1,c-c_{1}-1}$ with color $1,3$ , respectively.

Proof.

If $b_{1}<b$ and $1\leq c_{1}\leq c-3$ , then $b\geq r(P_{b_{1}+1},K_{1,b-b_{1}})$ by Theorem 2.3, and $c\geq r(K_{1,c_{1}+1},K_{1,c-c_{1}-1})$ by Theorem 2.4. For $c_{1}=0$ , since $K_{1,c_{1}+1}$ is an edge, we also have that $c\geq r(K_{1,c_{1}+1},K_{1,c-c_{1}-1})$ . Since $G[B]$ does not contain a monochromatic copy of $P_{b_{1}+1}$ and $G[C]$ does not contain a monochromatic copy of $K_{1,c_{1}+1}$ with color $2$ by the choice of $P^{*}$ and $S$ , it follows that $G[B]$ and $G[C]$ contain a monochromatic copies of $K_{1,b-b_{1}}$ and $K_{1,c-c_{1}-1}$ with color $1,3$ , respectively. If $b_{1}=b$ or $c-2\leq c_{1}\leq c-1$ , then $G[B]$ and $G[C]$ contain a monochromatic copies of $K_{1,b-b_{1}}$ and $K_{1,c-c_{1}-1}$ with color $1,3$ , respectively. So, $G[B]$ and $G[C]$ contain a monochromatic copies of $K_{1,b-b_{1}}$ and $K_{1,c-c_{1}-1}$ with color $1,3$ , respectively. ∎

We use $S^{B,1}$ and $S^{C,3}$ to denote monochromatic copies of $K_{1,b-b_{1}},K_{1,c-c_{1}-1}$ with color $1,3$ , respectively. Moreover, suppose that the center of $S^{B,1}$ and $S^{C,3}$ are $u_{1},u_{2}$ , respectively.

Claim 8.

$b-b_{1}<\lfloor\frac{n}{2}\rfloor$ and $c-c_{1}-1<\lfloor\frac{n}{2}\rfloor$ . Moreover, if $b\geq\frac{n}{2}$ , then $c_{1}<\lfloor\frac{n}{2}\rfloor$ .

Proof.

If $b-b_{1}\geq\lfloor\frac{n}{2}\rfloor$ , then since $|A|\geq\frac{n}{2}$ , there is a monochromatic $P_{n}$ with color $1$ between $V(S)-u_{1}$ and $A$ , and hence $G$ contains a monochromatic copy of $\widehat{K}_{n}$ with color $1$ , a contradiction. As the same reason, we have $c-c_{1}-1<\lfloor\frac{n}{2}\rfloor$ ; otherwise, there is a monochromatic $\widehat{K}_{n}$ with color $3$ , a contradiction. Moreover, if $b\geq\frac{n}{2}$ , then $c_{1}<\lfloor\frac{n}{2}\rfloor$ ; otherwise, there is a monochromatic $\widehat{K}_{n}$ with color $2$ , a contradiction. ∎

Let $a_{1}=n-2b+2b_{1}$ and $a_{2}=n-2c+2c_{1}+2$ . Then by Claim 8, $a_{1},a_{2}\geq 2$ . We have the following claim.

Claim 9.

There is no monochromatic $P_{a_{2}}$ with color $3$ in $G[A]$ .

Proof.

We first prove that $a-n+c-c_{1}-1\geq 0$ . If $a\geq n$ , then the result follows. If $b<\frac{n}{2}$ , then $b+c_{1}\leq b+c-1\leq 2b-1\leq n-2$ and hence

	$\displaystyle a-n+c-c_{1}-1$	$\displaystyle\geq\left(\left\lfloor\frac{5n}{2}\right\rfloor-1-b\right)-n-c_{1}-1$
		$\displaystyle=\left\lfloor\frac{3n}{2}\right\rfloor-(b+c_{1})-2$
		$\displaystyle\geq\left\lfloor\frac{3n}{2}\right\rfloor-n\geq 0.$

For the case $a<n$ and $b\geq\frac{n}{2}$ , by Claim 8, $c_{1}\leq\lfloor\frac{n}{2}\rfloor-1$ . Moreover, $\frac{n}{2}\leq b<n$ since $a\geq b$ . Let $b=n-q$ . Then $q\geq 1$ . So,

a-n+c-c_{1}-1\geq(\lfloor 5n/2\rfloor-1-b)-n-c_{1}-1=\lfloor n/2\rfloor+q-c_{1}-2\geq 0,

as desired.

Assume, to the contrary, that $G[A]$ contains a monochromatic $P=P_{a_{2}}$ with color $3$ (say one endpoint of $P$ is $w$ ). Then

|A-V(P)|\geq a-n+2c-2c_{1}-2=(a-n+c-c_{1}-1)+(c-c_{1}-1)\geq c-c_{1}-1.

We can choose a subset $A^{\prime}$ of $A-V(P)$ with $|A^{\prime}|=c-c_{1}-1$ . Since $|A^{\prime}|=|V(S^{C,3})-u_{2}|$ , there is a monochromatic $P^{\prime}$ of order $2|A^{\prime}|$ between $A^{\prime}$ and $V(S^{C,3})-u_{2}$ (say one endpoint of $P^{\prime}$ is $w^{\prime}$ ). Then $P^{\prime\prime}=P\cup P^{\prime}\cup\{ww^{\prime}\}$ is a monochromatic $P_{n}$ with color $3$ , and hence $u_{2}\vee P^{\prime\prime}$ a monochromatic $\widehat{K}_{n}$ with color $3$ , a contradiction. ∎

Case 1 $c_{1}+b\geq n$ .

The following claim is useful for the calculation.

Claim 10.

$b_{1}+2c_{1}\leq n-1$ .

Proof.

Suppose, to the contrary, that $b_{1}+2c_{1}\geq n$ . Then $n-2c_{1}\leq b_{1}$ . We can choose a subpath $P^{\prime}$ of $P^{*}$ such that $|P^{\prime}|=n-2c_{1}$ (say one endpoint of $P^{\prime}$ is $a$ ). Since $c_{1}+b\geq n$ , it follows that $|B-V(P^{\prime})|=b-(n-2c_{1})\geq c_{1}$ . Choose a subset $Y$ of $B-V(P^{\prime})$ such that $|Y|=|X|=c_{1}$ (recall that $X$ is the set of leaves of the maximum star $S$ in $H_{2}$ ). Then there is a monochromatic path $P^{\prime\prime}$ with color $2$ between $X$ and $Y$ (say $x\in X$ is an endpoint of $P^{\prime\prime}$ ), and so $u_{0}\vee(P^{\prime}\cup P^{\prime\prime}\cup\{ax\})$ is a monochromatic copy of $\widehat{K}_{n}$ with color $2$ , a contradiction. ∎

We have proved that $G[A]$ does not contain a monochromatic copy of $P_{a_{2}}$ with color $3$ in Claim 9. In this case, we have the following claim.

Claim 11.

There is no monochromatic copy of $P_{a_{1}}$ with color $1$ in $G[A]$ .

Proof.

Assume, to the contrary, that $G[A]$ contains a monochromatic copy of $P=P_{a_{1}}$ with color $1$ (say one endpoint of $P$ is $w$ ). Then $|A-V(P)|\geq a-n+2b-2b_{1}$ . We first prove that $a-n+b-b_{1}\geq 0$ . Since $c-c_{1}-1<\lfloor\frac{n}{2}\rfloor$ by Claim 8, it follows that $c\leq\lfloor\frac{n}{2}\rfloor+c_{1}$ , and hence

	$\displaystyle a-n+b-b_{1}$	$\displaystyle\geq\left(\left\lfloor\frac{5n}{2}\right\rfloor-1-c\right)-n-b_{1}=\left\lfloor\frac{3n}{2}\right\rfloor-(c+b_{1})-1$
		$\displaystyle\geq\left\lfloor\frac{3n}{2}\right\rfloor-\left(\left\lfloor\frac{n}{2}\right\rfloor+c_{1}+b_{1}\right)-1$
		$\displaystyle=n-[(b_{1}+2c_{1})-c_{1}]-1$
		$\displaystyle\geq n-[(n-1)-c_{1}]-1=c_{1}\geq 0,$

as desired. Recall that

|A-V(P)|\geq a-n+2b-2b_{1}=(a-n+b-b_{1})+(b-b_{1})\geq b-b_{1}.

We can choose a subset $A^{\prime}$ of $A$ such that $|A^{\prime}|=b-b_{1}$ . Since $|A^{\prime}|=|V(S^{B,1})-u_{1}|$ , there is a monochromatic $P^{\prime}$ of order $2|A^{\prime}|$ between $A^{\prime}$ and $V(S^{B,1})-u_{1}$ (say one endpoint of $P^{\prime}$ is $w^{\prime}$ ). Then $P^{\prime\prime}=P\cup P^{\prime}\cup\{ww^{\prime}\}$ is a monochromatic $P_{n}$ with color $1$ , and hence $u_{1}\vee P^{\prime\prime}$ a monochromatic $\widehat{K}_{n}$ with color $1$ , a contradiction. ∎

By Claims 9 and 11, we have $|A|=a<r(P_{a_{1}},P_{a_{2}})$ . However, if $a_{1}>a_{2}$ , then

	$\displaystyle r(P_{a_{1}},P_{a_{2}})$	$\displaystyle=a_{1}+\left\lfloor\frac{a_{2}}{2}\right\rfloor-1=\left\lfloor\frac{3n}{2}\right\rfloor-(b+c)-b+2b_{1}+c_{1}$
		$\displaystyle\leq\left\lfloor\frac{3n}{2}\right\rfloor-\left(\left\lfloor\frac{5n}{2}\right\rfloor-1-a\right)-b+2b_{1}+c_{1}$
		$\displaystyle=a-n-(b-b_{1})+(b_{1}+c_{1})+1.$

Since $b\geq b_{1}$ and $b_{1}+2c_{1}<n$ , we have $r(P_{a_{1}},P_{a_{2}})\leq a$ , a contradiction. If $a_{1}\leq a_{2}$ , then

	$\displaystyle r(P_{a_{1}},P_{a_{2}})$	$\displaystyle=a_{2}+\left\lfloor\frac{a_{1}}{2}\right\rfloor-1=\left\lfloor\frac{3n}{2}\right\rfloor-(b+c)-c+2c_{1}+b_{1}+1$
		$\displaystyle\leq\left\lfloor\frac{3n}{2}\right\rfloor-\left(\left\lfloor\frac{5n}{2}\right\rfloor-1-a\right)-c+(2c_{1}+b_{1})+1$
		$\displaystyle\leq(a-n)-c+(n-1)+2\leq a,$

a contradiction.

Case 2 $c_{1}+b<n$ .

By Claim 9, $G[A]$ does not contain monochromatic $P_{a_{2}}$ with color $3$ . Let

a^{\prime}=a-a_{2}+1=a-n+2c-2c_{1}-1.

Since $a\geq r(P_{a_{2}},K_{1,a^{\prime}})$ , it follows that $G[A]$ contains a monochromatic copy of $S^{*}=K_{1,a^{\prime}}$ with color $1$ . Note that

a^{\prime}\geq\left(\left\lfloor\frac{5n}{2}\right\rfloor-1-b-c\right)-n+2c-2c_{1}-1=\left\lfloor\frac{3n}{2}\right\rfloor-b+c-2c_{1}-2.

Since $c_{1}+b<n$ , it follows that $a^{\prime}\geq\lfloor\frac{n}{2}\rfloor-c_{1}+c-1\geq\lfloor\frac{n}{2}\rfloor$ . Let $u^{*}$ be the center of $S^{*}$ and $U^{*}$ be the set of leaves of $S^{*}$ . Then $|U^{*}|=a^{\prime}\geq\lfloor\frac{n}{2}\rfloor$ . Since $b\geq\frac{n}{2}$ , there is a monochromatic $P=P_{n}$ with color $1$ between $A$ and $U^{*}$ . Hence, $u^{*}\vee P$ is a monochromatic copy of $\widehat{K}_{n}$ with color $1$ , a contradiction. ∎

Proof of Theorem 1.10: If $n\geq 5$ , then the result follows immediately from Lemmas 5.1 and 5.2.

If $n\in\{2,3\}$ , then let $N=\lfloor\frac{5n}{2}\rfloor$ . Let $\Gamma\in\mathcal{B}_{3}(N)$ be an edge-coloring of $G=K_{N}$ with parts $A_{1},A_{2}$ and $|A_{1}|\geq|A_{2}|$ . Then $|A_{1}|\geq 4$ when $n=3$ and $|A_{1}|=3$ when $n=2$ . Suppose that each edge of $G[A_{i}]$ is colored by $1$ or $i+1$ , and the edges between $A_{1}$ and $A_{2}$ are colored by $1$ . Let $H$ be the subgraph of $G[A]$ induced by edges with color $1$ . For $n=3$ , if $\Delta(H)\geq 2$ or $\Delta(H)=1$ and $|A_{2}|\geq 2$ , then there is a monochromatic copy of $\widehat{K}_{3}$ with color $1$ ; if $\Delta(H)=0$ or $\Delta(H)=1$ and $|A_{2}|=1$ , then there is a monochromatic copy of $\widehat{K}_{3}$ with color $2$ . For $n=2$ , if $\Delta(H)\geq 1$ , then there is a monochromatic copy of $\widehat{K}_{2}$ with color $1$ ; if $\Delta(H)=0$ , then there is a monochromatic copy of $\widehat{K}_{2}$ with color $2$ . Thus, we have that $b_{3}(\widehat{K}_{n})\leq N$ for $n\in\{2,3\}$ . Let $\Gamma_{1}$ (resp. $\Gamma_{2}$ ) be an edge-coloring of $K_{4}$ (resp. $K_{6}$ ) such that the monochromatic graphs induced by color $1,2$ and $3$ are $K_{2,2}$ , $K_{2}$ and $K_{2}$ (resp. $K_{3,3}$ , $K_{3}$ and $K_{3}$ ), respectively. Then $\Gamma_{1}\in\mathcal{B}_{3}(4)$ (resp. $\Gamma_{2}\in\mathcal{B}_{3}(6)$ ) but there is not a monochromatic copy of $\widehat{K}_{2}$ (resp. $\widehat{K}_{3}$ ). Therefore, we have $b_{3}(\widehat{K}_{n})=\lfloor\frac{5n}{2}\rfloor$ for $n\in\{2,3\}$ .

If $\gamma\in\mathcal{T}(N)$ is an edge-coloring of $K_{N}$ with the maximum part $A$ , then $|A|\geq n$ , and hence $G[A]$ contains a monochromatic copy of $P_{n}$ with color $1$ or $3$ , and so $G$ contains a monochromatic copy of $\widehat{K}_{n}$ , and hence $\operatorname{gr}_{3}(K_{1,3}:\widehat{K}_{n})=\lfloor\frac{5n}{2}\rfloor$ for $n\in\{2,3\}$ .

6 Acknowledgements

We gratefully thank the anonymous reviewers for their careful reading of our manuscript and their valuable comments and suggestions. This paper is supported by the National Natural Science Foundation of China (Nos. 12201375, 12061059)

References

[1] J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer, 2008.
[2] V. Chvátal, F. Harary, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41(2) (1972), 335–345.
[3] F.R.K. Chung, R.L. Graham, Edge-colored complete graphs with precisely colored subgraphs, Combinatorica 3 (1983), 315–324.
[4] P. Erdős, R.J. McEliece, H. Taylor, Ramsey bounds for graph products, Pacific J. Math. 37(1) (1971), 45–46.
[5] R.J. Faudree, R.H. Schelp, Ramsey numbers for all linear forests, Discrete Math. 16 (1976), 149–155.
[6] J. Fox, A. Grinshpun, J. Pach, The Erdös-Hajnal conjecture for rainbow triangles, J. Combin. Theory Ser. B 111 (2015), 75–125.
[7] S. Fujita, C. Magnant, Extensions of Gallai-Ramsey results, J. Graph Theory 70(4) (2012), 404–426.
[8] S. Fujita, C. Magnant, K. Ozeki, Rainbow generalizations of Ramsey theory-A dynamic survey, Theory Appl. Graphs. 0(1), Article 1, (2014)
[9] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66.
[10] L. Gerencsér, A. Gyárfás, On Ramsey-Type Problems, Annales Universitatis Scientiarum Budapestinensis, Eötvös Sect. Math. 10 (1967), 167–170.
[11] A. Gyárfás, J. Lehel, R.H. Schelp, Z.S. Tuza, Ramsey numbers for local colorings, Graphs Combin. 3 (1987), 267–277.
[12] A. Gyárfás, G.N. Sárközy, A. Sebö, S. Selkow, Ramsey-type results for Gallai colorings, J. Graph Theory, 64 (2010), 233–243.
[13] A. Gyárfás, G. Simonyi, Edge colorings of complete graphs without tricolored triangles. J. Graph Theory 46(3) (2004), 211–216.
[14] F. Harary, Recent results on generalized Ramsey theory for graphs, Graph Theory and Applications, Springer, Berlin, 125–138 (1972)
[15] B. Li, Y. Zhang, H. Broersma, An exact formula for all star-kipas Ramsey numbers, Graphs Combin. 33 (1), 141–148.
[16] B. Li, Y. Zhang, H. Broersma, P. Holub, Closing the gap on path-kipas Ramsey numbers, Electron. J. Combin. 22(3) (2015), 3–21.
[17] H. Liu, C. Magnant, A. Saito, I. Schiermeyer, Y.T. Shi, Gallai-Ramsey number for $K_{4}$ , J. Graph Theory 94 (2020), 192–205.
[18] X. Li, L. Wang, X. Liu, Complete graphs and complete bipartite graphs without rainbow path, Discrete Math. 342 (2019), 2116–2126.
[19] E. Lucas, Récreations Mathématiqués, Vol. II. Gauthier-Villars, Paris, (1892)
[20] C. Magnant, P.S. Nowbandegani, Topics in Gallai-Ramsey theory, Springer Nature, Cham, Switzerland, 2020.
[21] C. Magnant, I. Schiermeyer, Gallai-Ramsey number for $K_{5}$ , J. Graph Theory 101(3) (2022), 455–492.
[22] T.D. Parsons, Path-star Ramsey numbers, J. Combin. Theory, Ser. B 17(1) (1974), 51–58.
[23] S.P. Radziszowski, Small Ramsey numbers, Electron. J. Combin., Dynamic Survey, 1–30 (1994)
[24] A.N.M. Salman, H.J. Broersma, Path-kipas Ramsey numbers, Discrete Applied Mathematics 155 (2007), 1878–1884
[25] A. Thomason, P. Wagner, Complete graphs with no rainbow path. J. Graph Theory 54 (3) (2007), 261–266.
[26] M. Wei, C. He, Y. Mao, X. Zhou, Gallai-Ramsey numbers for rainbow $P_{5}$ and monochromatic fans or wheels, Discrete Math. 345 (2022), 113092.

	$\displaystyle\|V_{1}\|$	$\displaystyle=a_{2}+\left\lfloor\frac{a_{1}}{2}\right\rfloor-1\leq a_{1}+\left\lfloor\frac{a_{2}}{2}\right\rfloor-1\leq a_{1}+\left\lfloor\frac{a_{1}-1}{2}\right\rfloor-1$
		$\displaystyle\leq n-2\|V_{2}\|+\left\lfloor\frac{n-2\|V_{2}\|-1}{2}\right\rfloor-1=n-3\|V_{2}\|+\left\lfloor\frac{n-3}{2}\right\rfloor$
		$\displaystyle\leq n-(N-\|V_{1}\|)-\|V_{2}\|+\left\lfloor\frac{n-3}{2}\right\rfloor$
		$\displaystyle\leq\|V_{1}\|-\|V_{2}\|<\|V_{1}\|,$

Ramsey and Gallai-Ramsey numbers for linear forests and kipas111Supported by the National Natural Science Foundation of China (Nos. 12201375, 12061059).

Abstract

1 Introduction

Definition 1.

Definition 2.

1.1 Ramsey and Gallai-Ramsey numbers

Theorem 1.1.

Theorem 1.2.

Definition 3.

Definition 4.

Conjecture 1.

1.2 Structural theorems and our methods

Theorem 1.3.

Remark 1.1.

Theorem 1.4 ([11]).

Theorem 1.5 ([11]).

Definition 5.

Definition 6.

Remark 1.2.

1.3 Progress and our results

Theorem 1.6.

Theorem 1.7.

Theorem 1.8.

Theorem 1.9.

Remark 1.3.

Theorem 1.10.

2 Preliminaries

Theorem 2.1.

Theorem 2.2.

Theorem 2.3.

Theorem 2.4.

Theorem 2.5.

Theorem 2.6.

Theorem 2.7.

Theorem 2.8.

Lemma 2.1.

Proof.

3 Technique results and the proof of Theorem 1.6

Lemma 3.1.

Proof.

Lemma 3.2.

Proof.

Claim 1.

Proof.

Fact 1.

Proof.

Claim 2.

Proof.

Claim 3.

Proof.

4 Proof of Theorems 1.7, 1.8 and 1.9

Lemma 4.1.

Proof.

Case 1.

Case 2.

Case 3.

Lemma 4.2.

Proof.

5 Proof of Theorem 1.10

Lemma 5.1.

Proof.

Claim 4.

Proof.

Claim 5.

Proof.

Claim 6.

Proof.

Lemma 5.2.

Proof.

Claim 7.

Proof.

Claim 8.

Proof.

Claim 9.

Proof.

Claim 10.

Proof.

Claim 11.

Proof.

6 Acknowledgements

Ramsey and Gallai-Ramsey numbers for linear forests and kipas¹¹1Supported by the National Natural Science Foundation of China (Nos. 12201375, 12061059).