# Lower Bounds for Multicolor Star-Critical Ramsey Numbers

Mark Budden  Department of Mathematics and Computer Science
Western Carolina University
Cullowhee, NC 28723 USA<EMAIL_ADDRESS>,  Yash Shamsundar Khobragade
Department of Mathematics
Indian Institute of Science Education and Research Bhopal
Bhopal 462066 India<EMAIL_ADDRESS>and  Siddhartha Sarkar  Department
of Mathematics
Indian Institute of Science Education and Research Bhopal
Bhopal 462066 India<EMAIL_ADDRESS>
###### Abstract.

The star-critical Ramsey number is a refinement of the concept of a Ramsey
number. In this paper, we give equivalent criteria for which the star-critical
Ramsey number vanishes. Next, we provide a new general lower bound for
multicolor star-critical Ramsey numbers whenever it does not vanish. As an
application, we evaluate $r_{*}(P_{k},P_{3},P_{3})$, where $P_{n}$ is a path
of order $n$. In the process of proving these results, we also show that
$r_{*}(C_{5},P_{3})=3$, where $C_{5}$ is a cycle of order $5$.

###### Key words and phrases:

multicolor Ramsey numbers, edge colorings, paths

###### 2020 Mathematics Subject Classification:

Primary 05C55, 05D10; Secondary 05C40

##  1\. Introduction

We assume that all graphs are finite and simple in that they do not contain
any loops or multiedges. For positive integers $s$ and $t$ such that $s\leq
t$, we write $[s,t]:=\\{i\in{\mathbb{N}}\ |\ s\leq i\leq t\\}$. The notations
$K_{n}$, $P_{n}$, and $C_{n}$ represent the complete graph, the path, and the
cycle of order $n$, respectively. A $t$-coloring of a graph $G=(V(G),E(G))$ is
a map

$f:E(G)\longrightarrow[1,t].$

Such an edge coloring is not assumed to be surjective nor is it assumed to be
proper (i.e., adjacent edges may receive the same color). For graphs
$G_{1},G_{2},\dots,G_{t}$, the Ramsey number $r(G_{1},G_{2},\dots,G_{t})$ is
the least natural number $p$ such that every $t$-coloring of the edges of
$K_{p}$ contains a subgraph that is isomorphic to $G_{i}$ in color $i$, for
some $i\in[1,t]$. A critical coloring for $r(G_{1},G_{2},\dots,G_{t})$ is a
$t$-coloring of $K_{r(G_{1},G_{2},\dots,G_{t})-1}$ that avoids a copy of
$G_{i}$ in color $i$, for all $i\in[1,t]$. The current known values of
multicolor Ramsey numbers can be found in Radziszowski’s dynamic survey [18].

In 2010, Jonelle Hook [13] introduced a refinement of the Ramsey number known
as a star-critical Ramsey number. In order to define it, we must first
introduce the notation $K_{n}\sqcup K_{1,k}$ to be the graph formed by taking
$K_{n}$, adding in a new vertex, then joining that vertex to exactly $k$
vertices in the $K_{n}$. The star-critical Ramsey number
$r_{*}(G_{1},G_{2},\dots,G_{t})$ is then defined to be the least $k$ such that
every $t$-coloring of $K_{r(G_{1},G_{2},\dots,G_{t})-1}\sqcup K_{1,k}$
contains a subgraph that is isomorphic to $G_{i}$ in color $i$, for some
$i\in[1,t]$. Note that

(1) $1\leq r_{*}(G_{1},G_{2},\dots,G_{t})\leq r(G_{1},G_{2},\dots,G_{t})-1,$

if the graphs $G_{1},G_{2},\dotsc,G_{t}$ are connected and of order at least
$2.$ In Section 2, we will completely determine the scenarios when
$r_{\ast}(G_{1},G_{2},\dots,G_{t})$ vanishes. In the special case where $t=1$,
we note that $r(G)=|V(G)|$ and $r_{*}(G)=\delta(G)$, where $\delta(G)$ is the
minimum degree of $G$:

$\delta(G):=\min\\{{\rm deg}_{G}(v)\ |\ v\in V(G)\\}.$

A proper vertex coloring of a graph $G$ is a map

$c:V(G)\longrightarrow\\{1,2,\dots\ell\\}$

such that $c(u)\neq c(v)$ when $uv\in E(G)$. The chromatic number of $G$,
denoted $\chi(G)$ is the least $\ell$ for which such a coloring exists. The
chromatic surplus of $G$, denoted $s(G)$ is the smallest order of a color
class among all proper vertex colorings of $G$ that use exactly $\chi(G)$
colors. Now let ${\mathcal{C}}$ denote the collection of all proper vertex
colorings of $G$ that admit a color class of size $s(G)$. For any
$c\in{\mathcal{C}}$, let $V_{1},V_{2},\dots,V_{\chi(G)}$ be the distinct color
classes in the coloring $c$, where

$s(G)=|V_{1}|\leq|V_{2}|\leq\cdots\leq|V_{\chi(G)}|.$

If $v\in V_{1}$, let ${\rm deg}_{V_{i}}(v)$ be the number of edges that join
$v$ to $V_{i}$, where $2\leq i\leq\chi(G)$. Then define

$\tau_{c}(G):=\min\\{{\rm deg}_{V_{i}}(v)\ |\ v\in V_{1}\ \mbox{and}\ 2\leq
i\leq\chi(G)\\}.$

and

$\tau(G):=\min\\{\tau_{c}(G)\ |\ c\in\mathcal{C}\\}.$

A graph is called connected if there exists a path joining every distinct pair
of vertices. If a graph is not connected, it is called disconnected, and the
maximal connected subgraphs are called its connected components. A connected
graph has one connected component. The vertex connectivity of a graph $G$,
denoted $\kappa(G)$, is the minimum number of vertices whose deletion results
in a disconnected graph or a single vertex.

In 1981, Burr [4] gave an improvement on Chvátal and Harary’s [5] lower bound
for $2$-color Ramsey numbers. To state Burr’s bound, let $c(G_{1})$ be the
order of a largest connected component of $G_{1}$. If $c(G_{1})\geq s(G_{2})$,
then

$r(G_{1},G_{2})\geq(c(G_{1})-1)(\chi(G_{2})-1)+s(G_{2}),$

and with this hypothesis a graph $G_{1}$ is called $G_{2}$-good if the
equality holds. More generally, if $r(G_{1},G_{2},\dotsc,G_{t-1})\geq
s(G_{t})$, then

(2) $\displaystyle
r(G_{1},G_{2},\dots,G_{t})\geq(r(G_{1},G_{2},\dots,G_{t-1})-1)(\chi(G_{t})-1)+s(G_{t}),$

and $(G_{1},G_{2},\dots,G_{t-1})$ is called $G_{t}$-good if equality holds.

This paper is organized as follows. In Section 2 we provide equivalent
criteria for which the star-critical Ramsey number vanishes (Theorem 4). In
Section 3, we provide an overview of the current known lower bounds for star-
critical Ramsey numbers (proved in [3], [9], [10], and [19]) and we offer an
improved multicolor lower bound (Theorem 12), as was initiated in [15]). To
demonstrate the utility of this new lower bound, we turn our attention in
Section 4 to the following evaluation (Theorem 15):

$r_{*}(P_{k},P_{3},P_{3})=\left\\{\begin{array}[]{ll}1&\mbox{if $k=3$}\\\
3&\mbox{if $k=4$}\\\ 4&\mbox{if $k=5$}\\\ 3&\mbox{if $k\geq
6$.}\end{array}\right.$

In the process of proving this result on paths, we also show that
$r_{*}(C_{5},P_{3})=3$.

##  2\. Star-Critical Ramsey Number Zero: An Exceptional Case

For a collection of graphs $G_{1},G_{2},\dotsc,G_{t}~{}(t\geq 2)$ of order at
least $2$, we will examine a situation where the star-critical Ramsey number
is $0$, as opposed to Inequality (1) in Section 1, where the graphs were
assumed to be connected. We must first introduce some notations and
terminologies.

A graph $G$ is called discrete if and only if $\chi(G)=1$, and it contains an
isolated vertex if and only if $\delta(G)=0$. If $G$ has order at least $2$ we
define

$G^{\prime}:=\begin{cases}G-w&\mbox{if
}\delta(G)=0{\mathrm{~{}and~{}}}{\mathrm{deg}}_{G}(w)=0\\\ G&\mbox{if
}\delta(G)\geq 1,\end{cases}$

where ${\mathrm{deg}}_{G}(w)$ denotes the degree of the vertex $w$ in the
graph $G$. Here, $G-w$ is the subgraph of $G$ induced by $V(G)-\\{w\\}$. Note
that $G^{\prime}$ is well-defined up to the isomorphism of graphs.

Let ${\mathcal{G}}$ denote the multiset
${\mathcal{G}}:=\\{G_{1},\dotsc,G_{t}\\}$. In the following, we will use the
notations $r({\mathcal{G}})$ and $r_{*}(\mathcal{G})$ to denote the Ramsey
number $r(G_{1},\dotsc,G_{t})$ and star-critical Ramsey number
$r_{\ast}(G_{1},\dotsc,G_{t})$, respectively. Let $I_{00}\subseteq
I_{0}\subseteq[1,t]$ be the subsets defined by

$\displaystyle I_{0}$ $\displaystyle:=$ $\displaystyle\\{i\in[1,t]\ |\
\delta(G_{i})=0\\},$ $\displaystyle I_{00}$ $\displaystyle:=$
$\displaystyle\\{i\in I_{0}\ |\ |V(G_{i})|=r({\mathcal{G}})\\}.$

Next, for a subset $J\subseteq[1,t]$, we define the multiset
${\mathcal{G}}^{\prime}_{J}=\\{F_{1},\dotsc,F_{t}\\}$ given by

$F_{i}:=\begin{cases}G^{\prime}_{i}&\mbox{if }i\in J,\\\ G_{i}&\mbox{if
}i\in[1,t]-J.\end{cases}$

The following lemma shows that removing a single isolated vertex from some of
the graphs in ${\mathcal{G}}$ might only change the Ramsey number by $1$.

######  Lemma 1.

Let $t\geq 2$ be an integer, and ${\mathcal{G}}=\\{G_{i}\ |\ i\in[1,t]\\}$ be
a multiset of simple graphs of order at least $2$. Then for any subset
$J\subseteq[1,t]$, we have $r({\mathcal{G}})-1\leq
r({\mathcal{G}}^{\prime}_{J})\leq r({\mathcal{G}})$.

###### Proof.

Without loss of generality, we may assume that $I_{0}\neq\emptyset$,
$J\subseteq I_{0}$ and $\emptyset\neq J=[1,k]$ for some $1\leq k\leq t$. Since
$G^{\prime}_{j}$ is a subgraph of $G_{j}$ for each $j\in J$, the second
inequality is immediate. We set $n:=r({\mathcal{G}})$, and assume that
$r({\mathcal{G}}^{\prime}_{J})=n-r<n$ for some $n-r\geq 1$. Then, we have
$1\leq r\leq n-1$. It is enough to show that $r=1$.

Assume that $r\geq 2$. Then, we have $n-r<n-r+1<n$. We will show that any
$t$-coloring of $K_{n-r+1}$ contains a monochromatic copy of $G_{i}$ is color
$i$, for some $i\in[1,t]$, which is a contradiction. Let ${\mathcal{H}}$ be a
$t$-coloring of $K_{n-r+1}$ that avoids a copy of $G_{i}$ in color $i$ for all
$i\in[1,t]-J$. Let $v$ be any vertex in $K_{n-r+1}$, and consider the
restriction ${\overline{\mathcal{H}}}$ of ${\mathcal{H}}$ to the subgraph
$K_{n-r+1}-v\cong K_{n-r}$. Since $r({\mathcal{G}}^{\prime}_{J})=n-r$, it
follows that $K_{n-r+1}-v$ contains a copy of $G^{\prime}_{j}$ in color $j$,
say $K$ in the $t$-coloring ${\overline{\mathcal{H}}}$ for some $j\in J$. Then
the disjoint union $K\cup v$ is a subgraph of $K_{n-r+1}$, which is a
monochromatic copy of $G_{j}$ in color $j$ in the $t$-coloring
${\mathcal{H}}$. This contradicts the inequality $n-r+1<r({\mathcal{G}})$,
from which it follows that $r=1$. ∎

In the following two examples, observe that both of the bounds for the Ramsey
number $r({\mathcal{G}}^{\prime}_{J})$ given in the above lemma can occur. Our
examples include the known Ramsey numbers $r(P_{3},K_{1,3})=5$ [17] and
$r(P_{3},P_{4})=4$ [12].

######  Example 2.

Let $G_{1}=P_{3}$, $G_{2}=K_{1,3}\cup w$, and $G^{\prime}_{2}=G_{2}-w$ (see
$(i)$, $(ii)$, and $(iii)$ in Figure 1) and we claim that
$r(G_{1},G_{2})=r(G_{1},G^{\prime}_{2})=5$.

Figure 1. Showing that $r(P_{3},K_{1,3}\cup w)=r(P_{3},K_{1,3})=5$.

The $2$-coloring of $K_{4}$ shown in $(iv)$ of Figure 1 avoids a red $G_{1}$
and a blue $G_{2}$ (and hence, a blue $G^{\prime}_{2}$). This implies that
$r(G_{1},G_{2})\geq 5$ and $r(G_{1},G^{\prime}_{2})\geq 5$. To verify
$r(G_{1},G_{2})=r(G_{1},G^{\prime}_{2})=5$, consider a red-blue coloring of
$K_{5}$ that avoids a red copy of $G_{1}$. Then there are at most two disjoint
red edges, leaving a vertex $v$ which is joined to the remaining vertices by
blue edges (see $(v)$ in Figure 1). The result is a $2$-coloring that contains
a blue $G_{2}$ (and hence, a blue $G_{2}^{\prime}$). It follows that
$r(G_{1},G_{2})=r(G_{1},G_{2}^{\prime})=5$.

######  Example 3.

Consider $G_{1}=P_{3},G_{2}=P_{4}\cup w$, and $G^{\prime}_{2}=G_{2}-w$ (see
$(i)$, $(ii)$, and $(iii)$ in Figure 2), and we claim that
$r(G_{1},G^{\prime}_{2})=4$, whereas $r(G_{1},G_{2})=5$.

Figure 2. The $2$-colorings corresponding to $r(P_{4},P_{4}\cup w)=5$ and
$r(P_{3},P_{4})=4$.

Recall that $r(G_{1},G^{\prime}_{2})=r(P_{3},P_{4})=4$. Since, $|V(G_{2})|=5$
and a blue $K_{4}$ does not contain a red $G_{1}$, we have $r(G_{1},G_{2})\geq
5$ (see $(iv)$ in Figure 2). Now we will show that $r(G_{1},G_{2})=5$. We
consider a red-blue coloring of $K_{5}$ that avoids a red copy of $G_{1}$. If
a red $P_{3}$ is avoided, then there are at most two disjoint red edges and
the remaining edges are blue. Then it contains a blue $P_{4}$ which is
extendible to a copy of a blue $G_{2}$ (see $(v)$ in Figure 2).

Now we are ready to prove a theorem which provides equivalent criteria for
when $r_{\ast}({\mathcal{G}})$ attains the value $0$.

######  Theorem 4.

Let $t\geq 2$ be an integer and ${\mathcal{G}}=\\{G_{i}\ |\ i\in[1,t]\\}$ be a
multiset of simple graphs of order at least $2$. Then
$r_{\ast}({\mathcal{G}})=0$ if and only if one of the following statements
hold:

  1. (i)

$G_{j}$ is discrete for some $j\in[1,t]$,

  2. (ii)

$G_{1},\dotsc,G_{t}$ are non-discrete graphs and
$r({\mathcal{G}}_{I_{00}})=r({\mathcal{G}})-1$.

###### Proof.

($\Longleftarrow$) First assume that (i) is true. We claim that

(3) $r({\mathcal{G}})=\min\big{\\{}|V(G_{i})|\ |\ G_{i}\mbox{ is discrete and
}i\in[1,t]\big{\\}}.$

Let $j_{0}\in[1,t]$ be chosen such that $G_{j_{0}}$ is discrete, and

$|V(G_{j_{0}})|=\min\big{\\{}|V(G_{i})|\ |\ G_{i}\mbox{ is discrete and
}i\in[1,t]\big{\\}}.$

Since a $K_{|V(G_{j_{0}})|-1}$ with all edges colored $i$ is a $t$-coloring
which avoids a copy $G_{i}$ in color $i$, for all $i\in[1,t]$, it follows that
$r({\mathcal{G}})\geq|V(G_{j_{0}})|$. Next, for any integer
$k\geq|V(G_{j_{0}})|$, every $t$-coloring of $K_{k}$ contains a copy of the
discrete graph $G_{j_{0}}$ in color $j_{0}$. This implies that
$r({\mathcal{G}})\leq|V(G_{j_{0}})|$, and Equation (3) follows.

Let $i_{0}\in[1,t]$ with $G_{i_{0}}$ discrete so that
$r({\mathcal{G}})=|V(G_{i_{0}})|$. Let ${\mathcal{H}}$ be an arbitrary
critical coloring of $K_{|V(G_{i_{0}})|-1}$; that is, $\mathcal{H}$ is a
$t$-coloring of $K_{|V(G_{i_{0}})|-1}$ that avoids a copy of $G_{i}$ in color
$i$, for all $i\in[1,t]$. Introduce a new vertex $v$ and consider the disjoint
union ${\mathcal{H}}\cup v$. Since $G_{i_{0}}$ is discrete with
$|V(G_{i_{0}})|$ many vertices, ${\mathcal{H}}\cup v$ contains a copy of
$G_{i_{0}}$ in color $i_{0}$. Since ${\mathcal{H}}$ was arbitrary, we have
$r_{\ast}({\mathcal{G}})=0$.

Now we show that (ii) implies $r_{\ast}({\mathcal{G}})=0$. Set
$n:=r({\mathcal{G}})$, and consider a critical coloring ${\mathcal{H}}$ for
$r({\mathcal{G}})$; that is, $\mathcal{H}$ is a $t$-coloring of $K_{n-1}$
which avoids a copy of $G_{i}$ in color $i$, for every $i\in[1,t]$. Since
$n-1=r({\mathcal{G}}_{I_{00}})$, ${\mathcal{H}}$ contains a copy of
$G^{\prime}_{j_{0}}$ for some $j_{0}\in I_{00}$. By definition of $I_{00}$ and
${\mathcal{G}}_{I_{00}}$, $G_{j_{0}}$ contains an isolated vertex $w$ and
$|V(G_{j_{0}})|=r({\mathcal{G}})$. Introduce a new isolated vertex $v$ to the
critical coloring ${\mathcal{H}}$. Then this isolated vertex $v$ along with
the copy of $G^{\prime}_{j_{0}}$ in ${\mathcal{H}}$ is isomorphic to the
disjoint union $G^{\prime}_{j_{0}}\cup w\cong G_{j_{0}}$. Hence
${\mathcal{H}}\cup v$ contains a copy of $G_{j_{0}}$ in color $j_{0}$. Since
we started with an arbitrary critical coloring ${\mathcal{H}}$ of
$r({\mathcal{G}})$, it follows that $r_{\ast}({\mathcal{G}})=0$.

($\Longrightarrow$) We assume that $r_{\ast}({\mathcal{G}})=0$ and
$G_{1},\dotsc,G_{t}$ are non-discrete. From Lemma 1, we have
$r({\mathcal{G}})-1\leq r({\mathcal{G}}_{I_{00}})\leq r({\mathcal{G}})$. It
remains to prove that $r({\mathcal{G}}_{I_{00}})=r({\mathcal{G}})-1$. If
possible assume that $r({\mathcal{G}}_{I_{00}})=r({\mathcal{G}})=:n$. Consider
any critical coloring of ${\mathcal{G}}_{I_{00}}$; that is, a $t$-coloring
${\mathcal{Q}}$ of $K_{n-1}$ that avoids a copy of $G^{\prime}_{i}$
(respectively, $G_{i}$) in color $i$ for each $i\in I_{00}$ (respectively,
$i\in[1,t]-I_{00}$). Then ${\mathcal{Q}}$ is also a critical coloring of
${\mathcal{G}}$. Introduce an isolated vertex $v$ and define
${\overline{\mathcal{Q}}}:={\mathcal{Q}}\cup v$. Since
$r_{\ast}({\mathcal{G}})=0$, it follows that ${\overline{\mathcal{Q}}}$
contains a copy of $G_{\gamma}$ in ${\overline{\mathcal{Q}}}$ for some
$\gamma\in[1,t]$ and $\delta(G_{\gamma})=0$. Now, this implies that $\gamma\in
I_{0}$. If possible, suppose $\gamma\in I_{0}-I_{00}$. Then
$|V(G_{\gamma})|<n$ and replacing the vertex $v$ by a vertex from
${\mathcal{Q}}$, we have a copy of $G_{\gamma}$ in color $\gamma$ in
${\mathcal{Q}}$, a contradiction. Hence $\gamma\in I_{00}$. Now
$|V(G_{\gamma})|=r({\mathcal{G}})=n$, and still has an isolated vertex. In
this case, removing the isolated vertex from $G_{\gamma}$ yields
$G^{\prime}_{\gamma}$, which has a copy inside ${\mathcal{Q}}$ in color
$\gamma$, again a contradiction. ∎

Theorem 4 leads to the following corollary, which is used for certain
calculations in the next section.

######  Corollary 5.

Let $t\geq 2$ be an integer and ${\mathcal{G}}=\\{G_{i}\ |\ i\in[1,t]\\}$ be a
multiset of simple graphs of order at least $2$. Then we have the following.

  1. (i)

If $G_{j}$ is discrete for some $j\in[1,t]$, then

$r({\mathcal{G}})=\min\big{\\{}|V(G_{i})|\ |\ G_{i}\mbox{ is discrete and
}i\in[1,t]\big{\\}}.$

  2. (ii)

If $G_{1},\dotsc,G_{t}$ are non-discrete graphs and
$r({\mathcal{G}}_{I_{00}})=r({\mathcal{G}})-1$, then

$\displaystyle r({\mathcal{G}})$ $\displaystyle=\max\big{\\{}|V(G_{j})|\ |\
\delta(G_{j})=0\mbox{ and }j\in[1,t]\big{\\}}$
$\displaystyle>\max\big{\\{}|V(G_{j})|\ |\ \delta(G_{j})\geq 1\mbox{ and
}j\in[1,t]\big{\\}}.$

###### Proof.

Statement (i) is already observed in the first part of the proof of Theorem 4.
To prove Statement (ii), we first notice that $r_{\ast}({\mathcal{G}})=0$ from
Theorem 4. Next, we notice that $r({\mathcal{G}})\geq|V(G_{i})|$ for each
$i\in[1,t]$. To see this, for an arbitrary $i\in[1,t]$, consider the
$t$-coloring of $K_{|V(G_{i})|-1}$ with assigned color $i$ to every edge.
Since $G_{j}$ is non-discrete for every $j\in[1,t]$, this avoids a copy of
$G_{j}$ in color $j$ for every $j\in[1,t]$.

Now we establish the inequality in Statement (ii). If possible, suppose
$r({\mathcal{G}})=|V(G_{j})|$ for some $j\in[1,t]$ with $\delta(G_{j})\geq 1$.
Consider a $K_{|V(G_{j})|-1}$, assign the color $j$ to all its edges, and call
this $t$-coloring ${\mathcal{S}}$. From the previous paragraph, it follows
that ${\mathcal{S}}$ is a critical coloring of ${\mathcal{G}}$. Now, introduce
a new isolated vertex $v$. Since $r_{\ast}({\mathcal{G}})=0$, there must be a
copy $K$ of $G_{\alpha}$ in color $\alpha$ in ${\mathcal{S}}\cup v$ for some
$\alpha\in[1,t]$. Since all the edges of ${\mathcal{S}}\cup v$ has color $j$
and $G_{\alpha}$ is non-discrete, this forces $\alpha=j$. Since $G_{j}\cong
K\subseteq{\mathcal{S}}\cup v$ and $K\subsetneq{\mathcal{S}}$, this implies
that $v\in V(K)$ is an isolated vertex of $K$, and consequently, $G_{j}$ has
an isolated vertex. This contradicts $\delta(G_{j})\geq 1$.

Now we proceed to prove that

$r({\mathcal{G}})=\max\big{\\{}|V(G_{j})|\ |\ \delta(G_{j})=0\mbox{ and
}j\in[1,t]\big{\\}}.$

Since $r({\mathcal{G}})$ is an upper bound for $|V(G_{i})|$ for all
$i\in[1,t]$, as noted earlier, it is enough to show that the equality
$r({\mathcal{G}})=|V(G_{j})|$ occurs for some $j\in[1,t]$ with
$\delta(G_{j})=0$. Suppose this is not true (i.e.,
$r({\mathcal{G}})>|V(G_{j})|$ for all $j\in[1,t]$ with $\delta(G_{j})=0$). Set
$n:=r({\mathcal{G}})$, and consider an arbitrary critical coloring
${\mathcal{P}}$ of ${\mathcal{G}}$; i.e., a $t$-coloring of $K_{n-1}$ that
avoids a copy of $G_{j}$ in color $j$ for all $j\in[1,t]$. Introduce a new
isolated vertex $x$. Since $r_{\ast}({\mathcal{G}})=0$, then
${\mathcal{P}}\cup x$ contains a copy $L$ of $G_{\beta}$ for some
$\beta\in[1,t]$. Since $x$ is not joined to ${\mathcal{P}}$ by any edges in
${\mathcal{P}}\cup x$, we have $\delta(G_{\beta})=0$. Then $x\in V(L)$, and
let $w\in V(G_{\beta})$ be the vertex of $G_{\beta}$ that is identified with
vertex $x$. Now $G^{\prime}_{\beta}:=G_{\beta}-w\cong L-x$. From our
assumption, $|V(G^{\prime}_{\beta})|<n-1=|V({\mathcal{P}})|$. Hence, there
exists a vertex $z\in V({\mathcal{P}})-V(L)$. But then $(L-x)\cup
z\subseteq{\mathcal{P}}$ is a copy of $G_{\beta}$ in color $\beta$, giving a
contradiction. ∎

##  3\. General Lower Bounds

The first general lower bound proved for star-critical Ramsey numbers was due
to Zhang, Broersma, and Chen [19]. In 2016, they proved the following
$2$-color lower bound.

######  Theorem 6 ([19]).

Suppose that $G_{1}$ is a connected graph of order at least $2$ that is
$G_{2}$-good. If $s(G_{2})=1$, $\delta(G_{1})=1$, or $\kappa(G_{1})\geq 2$,
then

$r_{*}(G_{1},G_{2})\geq(|V(G_{1})|-1)(\chi(G_{2})-2)+s(G_{2})+\delta(G_{1})+\tau(G_{2})-2.$

In 2018, Hao and Lin (see [9] and [10]) offered the following variation on
Zhang, Broersma, and Chen’s lower bound.

######  Theorem 7 ([9], [10]).

Suppose that $G_{2}$ is a graph with $\chi(G_{2})\geq 2$ and let $G_{1}$ be a
connected graph satisfying $|V(G_{1})|\geq s(G_{2})+1$. Then

$r_{\ast}(G_{1},G_{2})\geq(|V(G_{1})|-1)(\chi(G_{2})-2)+\min\\{|V(G_{1})|,\delta(G_{1})+\tau(G_{2})-1\\}.$

If $\kappa(G_{1})\geq 2$ or $\delta(G_{1})=1$, then

$r_{*}(G_{1},G_{2})\geq(|V(G_{1})|-1)(\chi(G_{2})-2)+\min\\{|V(G_{1})|,\delta(G_{1})+\tau(G_{2})-1\\}+s(G_{2})-1.$

Theorems 6 and 7 have been used in the determination of various star-critical
Ramsey numbers involving cycles, fans, and other graphs. One limitation of
these lower bounds is that they are only $2$-color results. At present, only
one general lower bound is known for multicolor star-critical Ramsey numbers.
An equivalent result to the following theorem was proved by Budden and DeJonge
[3] in 2022 (see also Theorem 1.3 of [2]).

######  Theorem 8 ([3], [2]).

Suppose that $G_{1},G_{2},\dots,G_{t-1}$ are connected graphs of order at
least $2$. If $G_{t}$ is any graph such that $(G_{1},G_{2},\dots,G_{t-1})$ is
$G_{t}$-good and

$r(G_{1},G_{2},\dots,G_{t-1})\geq s(G_{t}),$

then

$\displaystyle r_{*}(G_{1},G_{2},\dots,G_{t-1},G_{t})\geq
r_{\ast}(G_{1},G_{2},\dots,G_{t-1})$
$\displaystyle+r(G_{1},G_{2},\dots,G_{t-1},G_{t})$
$\displaystyle-r(G_{1},G_{2},\dots,G_{t-1}).$

Before proving a generalized lower bound for star-critical Ramsey numbers, we
introduce the following definition.

######  Definition 9.

Let $t\geq 2$ be an integer, ${\mathcal{G}}=(G_{1},G_{2},\dotsc,G_{t})$ be a
multiset of graphs. We say that ${\mathcal{G}}$ satisfies Hypothesis A if the
following four conditions are satisfied:

  1. (1)

$|V(G_{i})|>1$ for all $i\in[1,t]$,

  2. (2)

$G_{i}$ is connected for all $i\in[1,t-1]$,

  3. (3)

$(G_{1},G_{2},\dots,G_{k-1})$ is $G_{k}$-good, for all $k\in[2,t]$, and

  4. (4)

$r(G_{1},G_{2},\dots,G_{k-1})\geq s(G_{k})+1$, for all $k\in[2,t]$.

In Theorem 10, we address the exceptional case $r_{\ast}({\mathcal{G}})=0$, as
discussed in the previous section.

######  Theorem 10.

Let $t\geq 2$ be an integer and ${\mathcal{G}}=(G_{1},G_{2},\dotsc,G_{t})$ be
a multiset of graphs that satisfies Hypothesis A. Then the following
statements are equivalent:

  1. (i)

$\chi(G_{t})=1$,

  2. (ii)

$r_{\ast}({\mathcal{G}})=0$.

###### Proof.

The statement (i)$\Longrightarrow$(ii) follows from Theorem 4. To prove
(ii)$\Longrightarrow$(i) we assume that $r_{\ast}({\mathcal{G}})=0$. Now
suppose (i) is not true (i.e., $\chi(G_{t})\geq 2$). If $G_{t}$ does not
contain an isolated vertex, then $I_{00}\subseteq I_{0}=\emptyset$ using the
notation in Section 2. From Theorem 4, we have
$r({\mathcal{G}})=r({\mathcal{G}}_{I_{00}})=r({\mathcal{G}})-1$, giving a
contradiction.

Now let $w\in V(G_{t})$ be an isolated vertex in $G_{t}$ and set
$G^{\prime}_{t}:=G_{t}-w$. Notice that $I_{0}=\\{t\\}$ and again as argued
above, we must have $I_{00}=\\{t\\}$ as well. Since $\chi(G_{t})\geq 2$, we
have $G_{1},G_{2},\dotsc,G_{t}$ are all non-discrete graphs. Then by part (ii)
of Corollary 5, it follows that
$r(G_{1},G_{2},\dotsc,G_{t-1},G^{\prime}_{t})=r(G_{1},G_{2},\dotsc,G_{t})-1$.
Now, using $\chi(G_{t})\geq 2$, we have $\chi(G_{t})=\chi(G^{\prime}_{t})$ and
$s(G_{t})=s(G^{\prime}_{t})$ since for any proper vertex coloring of $G_{t}$,
the set $\\{w\\}$ cannot form a color class. Next, using Hypothesis A we have

$\displaystyle r(G_{1},G_{2},\dotsc,G_{t})$ $\displaystyle=$
$\displaystyle(r(G_{1},G_{2},\dotsc,G_{t-1})-1)(\chi(G_{t})-1)+s(G_{t})$
$\displaystyle=$
$\displaystyle(r(G_{1},G_{2},\dotsc,G_{t-1})-1)(\chi(G^{\prime}_{t})-1)+s(G^{\prime}_{t})$

which implies that

$r(G_{1},G_{2},\dotsc,G_{t-1},G^{\prime}_{t})=(r(G_{1},G_{2},\dotsc,G_{t-1})-1)(\chi(G^{\prime}_{t})-1)+s(G^{\prime}_{t})-1.$

and the multiset $(G_{1},G_{2},\dotsc,G_{t-1},G^{\prime}_{t})$ also satisfies
the hypothesis required for Inequality (2). Then we also have

$r(G_{1},G_{2},\dotsc,G_{t-1},G^{\prime}_{t})\geq(r(G_{1},G_{2},\dotsc,G_{t-1})-1)(\chi(G^{\prime}_{t})-1)+s(G^{\prime}_{t}),$

giving a contradiction. ∎

Our next goal is to establish a general multicolor lower bound for star-
critical Ramsey numbers. Our new bound both extends Theorems 6 and 7 to the
multicolor setting and improves the bound given in Theorem 8 for certain
collections of graphs. In order to state it, we must iterate the process of
introducing graphs to Ramsey and star-critical Ramsey numbers.

######  Definition 11.

For a $t$-tuple of graphs $(G_{1},G_{2},\dots,G_{t})$, where $t\geq 2$, define
the characteristic sequence $\\{d_{k}\\}_{k=1}^{t}$ as follows. First let
$d_{1}=\delta(G_{1})-1$. Then for each $k\in[2,t]$, let
$R_{k-1}=r(G_{1},G_{2},\dots,G_{k-1})$ and define

$d_{k}=\left\\{\begin{aligned}
(R_{k-1}-1)&(\chi(G_{k})-2)+d_{k-1}+s(G_{k})+\tau(G_{k})-2\\\ &\mbox{if
$s(G_{k})=1$, $d_{k-1}=0$, or $\kappa(G_{i})\geq 2$ for all $i\in[1,k-1]$}\\\
(R_{k-1}-1)&(\chi(G_{k})-2)+\min\\{R_{k-1},\tau(G_{k})+d_{k-1}\\}-1\\\
&\mbox{if $1\leq s(G_{k})-1\leq d_{k-1}$ and $\kappa(G_{i})=1$ for some
$i\in[1,k-1]$}\\\ (R_{k-1}-1)&(\chi(G_{k})-2)+s(G_{k})+\tau(G_{k})-2\\\
&\mbox{if $1\leq d_{k-1}<s(G_{k})-1$ and $\kappa(G_{i})=1$ for some
$i\in[1,k-1]$}.\end{aligned}\right.$

######  Theorem 12.

Let $t\geq 2$ be an integer and ${\mathcal{G}}=(G_{1},G_{2},\dotsc,G_{t})$ be
a multiset of graphs that satisfies Hypothesis A. Assume that $\chi(G_{t})\geq
2$. Then

$r_{*}(G_{1},G_{2},\dots,G_{k})\geq d_{k}+1,$

for all $k\in[2,t]$.

###### Proof.

We proceed by induction on $k\geq 1$. In the base case $k=1$, we trivially
have $r_{*}(G_{1})=\delta(G_{1})=d_{1}+1$. Now let $2\leq k\leq t$ and assume
that $r_{*}(G_{1},G_{2},\dots,G_{k-1})\geq d_{k-1}+1$. Then there exists a
$(k-1)$-coloring of

$K_{r(G_{1},G_{2},\dots,G_{k-1})-1}\sqcup K_{1,d_{k-1}}$

that avoids a copy of $G_{i}$ in color $i$, for all $i\in[1,k-1]$. Denote this
$(k-1)$-colored graph by $\mathcal{G}_{1}$ and let $w$ be the vertex of degree
$d_{k-1}$. Denote by $\mathcal{G}_{2}$ the $(k-1)$-colored complete graph
formed by deleting vertex $w$ from $\mathcal{G}_{1}$. Let $D_{0}\subset
V(\mathcal{G}_{2})$ comprise of the $d_{k-1}$ vertices in $\mathcal{G}_{1}$
that are adjacent to $w$ (note that $D_{0}$ is a proper subset of
$V(\mathcal{G}_{2})$).

Let $\mathcal{G}_{3}$ be a subgraph of $\mathcal{G}_{2}$ induced on any subset
of $s(G_{k})-1$ vertices in $V(\mathcal{G}_{2})$. As
$|\mathcal{G}_{3}|=s(G_{k})-1\leq
r(G_{1},G_{2},\dotsc,G_{k-1})-2=|\mathcal{G}_{2}|-1$, there exists a vertex
$w^{\prime}\in V(\mathcal{G}_{2})-V(\mathcal{G}_{3})$. Let
$\mathcal{G}_{2}[V(\mathcal{G}_{3})\cup w^{\prime}]$ be the subgraph of
$\mathcal{G}_{2}$ which is induced by the vertices of $\mathcal{G}_{3}$ along
with $w^{\prime}$. Here,
$\mathcal{G}_{3}\subseteq\mathcal{G}_{2}[V(\mathcal{G}_{3})\cup
w^{\prime}]\subseteq\mathcal{G}_{2}\subseteq\mathcal{G}_{1}$ and all of them
avoid a copy of $G_{i}$ in color $i$, for all $i\in[1,k-1]$.

From Assumption (3) in the statement of Hypothesis A (Definition 9), it
follows that

$r(G_{1},G_{2},\dots,G_{k})=(r(G_{1},G_{2},\dots,G_{k-1})-1)(\chi(G_{k})-1)+s(G_{k}).$

In order to construct a critical coloring for $(G_{1},G_{2},\dots,G_{k})$,
begin with a copy of $K_{\chi(G_{k})}$ in color $k$ and replace one of its
vertices with a copy of $\mathcal{G}_{3}$ (name this vertex set
$X_{\chi(G_{k})}$) and the other $\chi(G_{k})-1$ of its vertices are replaced
with copies of $\mathcal{G}_{2}$ (name these vertex sets
$X_{1},X_{2},\dots,X_{\chi(G_{k})-1}$). The resulting

$K_{(r(G_{1},G_{2},\dots,G_{k-1})-1)(\chi(G_{k})-1)+s(G_{k})-1}$

avoids a monochromatic copy of $G_{i}$ in color $i$, for all $i\in[1,k-1]$
since every $G_{i}$ is assumed to be connected. To see that it also avoids a
copy of $G_{k}$ in color $k$, consider two cases. First, if $s(G_{k})=1$, then
coloring the vertices according to which copy of
$K_{r(G_{1},G_{2},\dots,G_{k-1})-1}$ they are in leads to a proper vertex
coloring of the subgraph spanned by edges in color $k$ that uses
$\chi(G_{k})-1$ colors. If $s(G_{k})>1$, then we obtain a proper vertex
coloring for the subgraph spanned by edges in color $k$ that uses
$\chi(G_{k})$ colors, but has a color class with only $s(G_{k})-1$ colors. In
both cases, we see that a copy $G_{k}$ in color $k$ does not exist. Hence, we
have produced a $k$-coloring of $K_{r(G_{1},G_{2},\dots,G_{k})-1}$ that avoids
a copy of $G_{i}$ in color $i$, for all $i\in[1,k]$. Introduce a vertex $v$ to
this critical coloring above, which will be the centre of the star. We divide
the remainder of the proof into cases.

Case 1 Assume that $s(G_{k})=1$, $d_{k-1}=0$, or $\kappa(G_{i})\geq 2$ for all
$1\leq i\leq k-1$. Join $v$ to vertices in
$X_{1},X_{2},\dots,X_{\chi(G_{k})-2}$ by edges in color $k$. Then
$X_{\chi(G_{k})-1}\cong\mathcal{G}_{2}$, and under this isomorphism let
$D\subset X_{\chi(G_{k})-1}$ correspond to $D_{0}$ and vertex $z_{i}\in D$
correpsond to vertex $y_{i}\in D_{0}$, for all $i\in[1,d_{k-1}]$. Join $v$ to
the vertices in $D$, coloring edge $vz_{i}$ the same color as edge $wy_{i}$,
for all $i\in[1,d_{k-1}]$. Similar to that of $\mathcal{G}_{1}$, this coloring
avoids a copy of $G_{j}$ in color $j$, for all $j\in[1,k-1]$.

Also, $X_{\chi(G_{k})}\cong\mathcal{G}_{3}$, and under this isomorphism, let
vertex $h_{i}\in X_{\chi(G_{k})}$ correspond to vertex $g_{i}\in
V(\mathcal{G}_{3})$, for all $i\in[1,s(G_{k})-1]$. Join $v$ to the vertices in
$X_{\chi(G_{k})}$, coloring edge $vh_{i}$ the same color as edge
$w^{\prime}g_{i}$, for all $i\in[1,s(G_{k})-1]$. Similar to that of
$\mathcal{G}_{2}[V(\mathcal{G}_{3})\cup w^{\prime}]$, this coloring avoids a
copy of $G_{j}$ in color $j$, for all $j\in[1,k-1]$.

Let $T\subseteq X_{\chi(G_{k})-1}-D$ be chosen such that

$|T|=\min\\{r(G_{1},G_{2},\dotsc,G_{k-1})-1-d_{k-1},\tau(G_{k})-1\\}.$

Join $v$ to the vertices in $T$ by edges in color $k$. Call this newly
constructed graph $L$ and note that there is no copy of $G_{k}$ in color $k$
in $L$. Denote by $L_{k}$ the subgraph of $L$ spanned by edges in color $k$.

Color the vertices in $X_{i}$ by color $c_{i}$ such that $c_{i}\neq c_{j}$,
for all $i,j\in[1,\chi(G_{k})]$ and $i\neq j$. As $v$ is not joined to
$X_{\chi(G_{k})}$ by any edges of color $k$, assign color $c_{\chi(G_{k})}$ to
$v$. This is a proper vertex coloring of $L_{k}$ using $\chi(G_{k})$ colors.
As $X_{i}$ is joined to $X_{j}$ by edges of color $k$ for all
$i,j\in[1,\chi(G_{k})]$ and $i\neq j$, this is the only possible vertex
coloring of $L_{k}$ using $\chi(G_{k})$ colors (up to a permutation of the
colors). Corresponding to this vertex coloring, $X_{\chi(G_{k})}\cup v$ is the
smallest color class and stays so, for all proper vertex colorings of $L_{k}$.
Thus,

$s(L_{k})=|X_{\chi(G_{k})}\cup v|=s(G_{k})-1+1=s(G_{k}).$

For each vertex $w_{i}\in X_{\chi(G_{k})}$, $w_{i}$ is connected to each of
the other color classes by $r(G_{1},G_{2},\dotsc,G_{k-1})-1$ many edges.
However, $v$ is connected to $X_{\chi(G_{k})-1}$ by

$|T|=\min\\{r(G_{1},G_{2},\dotsc,G_{k-1})-1-d_{k-1},\tau(G_{k})-1\\}$

many edges. Thus, $\tau(L_{k})=|T|\leq\tau(G_{k})-1$ implying $G_{k}\nsubseteq
L_{k}$. So, there is no copy of $G_{i}$ in color $i$ in $L$ for all
$i\in[1,k-1]$.

If $s(G_{k})=1$, then $X_{\chi(G_{k})}=\emptyset$. Hence, the
$\\{1,2,\dots,k-1\\}$ (edge) colored connected components have vertex sets
$X_{1},X_{2},\dotsc,X_{\chi(G_{k})-2},X_{\chi(G_{k})-1}\cup v$ individually,
which are nothing but copies of $\mathcal{G}_{2}$ and $\mathcal{G}_{1}$.
Hence, they avoid a copy of $G_{i}$ in color $i$ for all $i\in[1,k-1]$.

If $d_{k-1}=0$, then $D=\emptyset$ and $v$ is not joined to vertices in
$X_{\chi(G_{k})-1}$ by any edge of color ${1,2,\dotsc,k-1}$. Hence, the only
$\\{1,2,\dots,k-1\\}$ (edge) colored connected components have vertex sets
$X_{1},X_{2},\dotsc,X_{\chi(G_{k})-2},X_{\chi(G_{k})-1},X_{\chi(G_{k})}\cup
v$, which are nothing but copies of $\mathcal{G}_{2}$ and
$\mathcal{G}_{2}[V(\mathcal{G}_{3})\cup w^{\prime}]$. Hence, they avoid a copy
of $G_{i}$ in color $i$ for all $i\in[1,k-1]$.

If $s(G_{k})>1$ and $d_{k-1}\geq 1$, then assume that $\kappa(G_{i})\geq 2$
for all $i\in[1,k-1]$. If $L$ contains a copy of $G_{i}$ in color $i$ for some
$i\in[1,k-1]$, then from the above two cases it is clear that the copy of
$G_{i}$ must have at least one of it’s vertices in $X_{\chi(G_{k})}$ and at
least one vertex in $X_{\chi(G_{k})-1}$, implying $v$ to also be a vertex in
this copy of $G_{i}$. But $v$ is a cut-vertex, implying $\kappa(G_{i})=1$, a
contradiction. Hence, there is no copy of $G_{i}$ in color $i$ in $L$ for all
$i\in[1,k-1]$.

Thus, $L$ avoids a copy of $G_{j}$ in color $j$ for all $j\in[1,k]$. If
$\tau(G_{k})-1\geq r(G_{1},G_{2},\dotsc,G_{k-1})-1-d_{k-1}$ then $v$ is
connected to all the vertices in $K_{r(G_{1},\dotsc,G_{k})-1}$ and we have a
$k$-coloring of $K_{r(G_{1},G_{2},\dotsc,G_{k})}$. So this must contain a copy
of $G_{j}$ in color $j$, for some $j\in[1,k]$, giving a contradiction.

Hence, $\tau(G_{k})-1<r(G_{1},G_{2},\dotsc,G_{k-1})-1-d_{k-1}$ and
$|T|=\tau(G_{k})-1$, from which it follows that

$\begin{split}r_{*}(G_{1},G_{2},\dotsc,G_{k})\geq(r(G_{1},G_{2},\dotsc,G_{k-1})-1)(\chi(G_{k})-2)+s(G_{k})-1\\\
+d_{k-1}+\tau(G_{k})-1+1.\end{split}$

Thus, $r_{*}(G_{1},G_{2},\dotsc,G_{k})\geq d_{k}+1$.

Case 2 Assume that $1\leq s(G_{k})-1\leq d_{k-1}$ and $\kappa(G_{i})=1$ for
some $i\in[1,k-1]$. In this case, remove the edges joining $v$ to
$X_{\chi(G_{k})}$ in L. As we are not changing the construction of $k$ colored
edges, this new graph does not contain a copy of $G_{k}$ in color $k$. And all
the $\\{1,2,\dots,k-1\\}$ (edge) colored connected components have vertex sets
$X_{1},X_{2},\dotsc,X_{\chi(G_{k})-2},X_{\chi(G_{k})-1}\cup v$ individually,
which are just copies of $\mathcal{G}_{2}$ and $\mathcal{G}_{1}$. Hence, there
is no copy of $G_{j}$ in color $j$ for all $j\in[1,k]$. Thus,

$\begin{split}r_{*}(G_{1},G_{2},\dotsc,G_{k})&\geq(r(G_{1},G_{2},\dotsc,G_{k-1})-1)(\chi(G_{k})-2)+d_{k-1}+|T|+1\\\
&=(r(G_{1},G_{2},\dotsc,G_{k-1})-1)(\chi(G_{k})-2)+d_{k-1}\\\ &\hskip
14.22636pt+\min\\{r(G_{1},G_{2},\dotsc,G_{k-1})-1-d_{k-1},\tau(G_{k})-1\\}+1\\\
&=(r(G_{1},G_{2},\dotsc,G_{k-1})-1)(\chi(G_{k})-2)\\\ &\hskip
14.22636pt+\min\\{r(G_{1},G_{2},\dotsc,G_{k-1}),\tau(G_{k})+d_{k-1}\\}-1+1.\end{split}$

Thus, $r_{*}(G_{1},G_{2},\dotsc,G_{k})\geq d_{k}+1$.

Case 3 Assume that $1\leq d_{k-1}<s(G_{k})-1$ and $\kappa(G_{i})=1$ for some
$i\in[1,k-1]$. In this case, remove the edges joining $v$ to
$X_{\chi(G_{k})-1}$ in $L$. As $v$ is not joined to vertices in
$X_{\chi(G_{k})-1}$ by edges of color ${1,2,\dotsc,k-1}$, the only
$\\{1,2,\dots,k-1\\}$ (edge) colored connected components have vertex sets
$X_{1},\dots,X_{\chi(G_{k})-1}$ and $X_{\chi(G_{k})}\cup v$ individually,
which are just copies of $\mathcal{G}_{2}$ and
$\mathcal{G}_{2}[V(\mathcal{G}_{3})\cup w^{\prime}]$.

Here, instead of $T$, let $T_{1}\subseteq X_{\chi(G_{k})-1}$ such that
$|T_{1}|=\min\\{r(G_{1},G_{2},\dotsc,G_{k-1})-1,\tau(G_{k})-1\\}$. Join $v$ to
vertices in $T_{1}$ by edges of color $k$. Call this newly constructed graph
$\mathcal{L}$. Following the similar vertex coloring argument using
$\chi(G_{k})$ many colors as in Case I, we can conclude that
$\tau(\mathcal{L}_{k})\leq\tau(G_{k})-1$ implying that there is no copy of
$G_{k}$ in color $k$ in this construction. Thus, there is no copy of $G_{j}$
in color $j$ for all $j\in[1,k]$.

If $r(G_{1},G_{2},\dotsc,G_{k-1})-1\leq\tau(G_{k})-1$ then $v$ is connected to
all the vertices in $K_{r(G_{1},G_{2},\dotsc,G_{k})-1}$ and we have a
$k$-coloring of $K_{r(G_{1},G_{2},\dotsc,G_{k})}$. This coloring necessarily
contains a copy of $G_{j}$ in color $j$, for some $j\in[1,k]$, giving a
contradiction. Hence, $\tau(G_{k})-1<r(G_{1},G_{2},\dotsc,G_{k-1})-1$ and
$|T_{1}|=\tau(G_{k})-1$. Thus,

$\begin{split}r_{*}(G_{1},G_{2},\dotsc,G_{k})\geq(r(G_{1},G_{2},\dotsc,G_{k-1})-1)(\chi(G_{k})-2)+s(G_{k})-1\\\
+\tau(G_{k})-1+1,\end{split}$

from which it follows that $r_{*}(G_{1},G_{2},\dotsc,G_{k})\geq d_{k}+1$ ∎

##  4\. Some Star-Critical Ramsey Numbers for Paths

In 1967, Gerencsér and Gyárfás [12] proved that if $m\geq n\geq 2$, then

$r(P_{m},P_{n})=m+\left\lfloor\frac{n}{2}\right\rfloor-1.$

Hook [14] considered the star-critical analogue of this number by showing that
$r_{*}(P_{m},P_{n})=\left\lceil\frac{n}{2}\right\rceil$, for all $m\geq n\geq
2$. In the case of three colors, Maherani, Omidi, Raeisi, and Shahsiah [16]
proved that for all $m\geq n\geq 3$ and $(m,n)\neq(3,3),(4,3)$,

(4) $r(P_{m},P_{n},P_{3})=m+\left\lfloor\frac{n}{2}\right\rfloor-1.$

Note that $(P_{m},P_{n})$ is $P_{3}$-good for these values of $m$ and $n$. The
cases

$r(P_{3},P_{3},P_{3})=5=r(P_{4},P_{3},P_{3})$

can be found in [1].

Theorem 12 implies that if $m\geq n\geq 3$ and $(m,n)\neq(3,3),(4,3)$, then

(5) $r_{*}(P_{m},P_{n},P_{3})\geq\left\lceil\frac{n}{2}\right\rceil+1.$

We also need the following well-known factorization theorem. Recall that a
$1$-factor of a graph $G$ is an independent set of edges that span $G$. A
graph is said to have a $1$-factorization if its edge set is the disjoint
union of $1$-factors.

######  Theorem 13 ([11]).

If $n$ is even, then the complete graph $K_{n}$ has a $1$-factorization.

Using the main result of [7], we have $r(C_{5},P_{3})=5$ and
$r(C_{4},P_{3})=4$. In the following theorem we determine
$r_{\ast}(C_{5},P_{3})$, which we will be needed for the main result of this
section.

######  Theorem 14.

$r_{\ast}(C_{5},P_{3})=3$.

###### Proof.

Theorem 6 implies that $r_{\ast}(C_{5},P_{3})\geq 3$. To prove the reverse
inequality, consider a $2$-coloring of $K_{4}\sqcup K_{1,3}$ using red and
blue and let $w$ be the centre vertex of the star. Since $r(C_{4},P_{3})=4$,
if the $K_{4}$-subgraph does not contain a blue $P_{3}$, then it must contain
a red $C_{4}$, which we assume is given by $abcda$. As we are to avoid a blue
$P_{3}$, at least $2$ red edges are adjacent to $w$.

If $w$ is adjacent with red edges to two vertices in the red $C_{4}$ (say
$\\{a,d\\}$), then $wabcdw$ is a red $C_{5}$ (see image (i) in Figure 3).

Figure 3. $2$-colorings of $K_{4}\sqcup K_{1,3}$ that shows
$r_{*}(C_{5},P_{3})\leq 3$

If $w$ is adjacent with red edges to two non-adjacent diagonal vertices of the
red $C_{4}$ (say $\\{a,c\\}$), then we consider the colors of $ac$ and $bd$.

If both of $ac$ and $bd$ are red, then $wabdcw$ is a red $C_{5}$ (see image
(ii) in Figure 3). The same argument holds if $ac$ is blue and $bd$ is red
(see image (iii) in Figure 3). If $ac$ is red and $bd$ is blue, then $w$ must
also be adjacent to either $b$ or $d$ by a red edge (say $d$), then $wabcdw$
is a red $C_{5}$ (see image (iv) in Figure 3). The same argument holds if $ac$
and $bd$ are both are blue (see image (v) in Figure 3). In all cases, we find
that there is a red $C_{5}$ or a blue $P_{3}$, from which it follows that
$r_{*}(C_{5},P_{3})\leq 3$. ∎

######  Theorem 15.

If $k\geq 3$, then

$r_{*}(P_{k},P_{3},P_{3})=\left\\{\begin{array}[]{ll}1&\mbox{if $k=3$}\\\
3&\mbox{if $k=4$}\\\ 4&\mbox{if $k=5$}\\\ 3&\mbox{if $k\geq
6$.}\end{array}\right.$

###### Proof.

We break the proof up into the cases indicated in the statement of the
theorem.

Case 1 Assume that $k=3$ so that $r(P_{3},P_{3},P_{3})=5$. Consider a
$3$-coloring of $K_{4}\sqcup K_{1,1}$ and let vertex $x$ be the unique vertex
of degree $4$. By the Pigeonhole Principle, at least two of the edges incident
with $x$ must be the same color, forming a monochromatic $P_{3}$. It follows
that $r_{*}(P_{3},P_{3},P_{3})=1$.

Case 2 Assume that $k=4$ so that $r(P_{4},P_{3},P_{3})=5$. By Theorem 13, the
complete graph $K_{4}$ can be factored into three $1$-factors. Color each
$1$-factor with a unique color from red, blue, and green with edges $ad$ and
$bc$ being red. Introduce vertex $v$ and the red edges $va$ and $vd$. The
resulting $K_{4}\sqcup K_{1,2}$ avoids a red $P_{4}$, a blue $P_{3}$, and a
green $P_{3}$ (see Figure 4).

Figure 4. A $3$-coloring of $K_{4}\sqcup K_{1,2}$ that avoids a red $P_{4}$, a
blue $P_{3}$, and a green $P_{3}$.

It follows that $r_{*}(P_{4},P_{3},P_{3})\geq 3$. In the process of proving
the reverse inequality, we will show that this coloring is unique if a red
$P_{4}$, a blue $P_{3}$, and a green $P_{3}$ are to be avoided.

Now consider a $3$-coloring of $K_{4}\sqcup K_{1,3}$ (using red, blue, and
green) and let $v$ be the center vertex of the star. If any color is missing
in the $K_{4}$, then the Ramsey numbers $r(P_{3},P_{3})=3$ and
$r(P_{4},P_{3})=4$ imply that there is a red $P_{4}$, a blue $P_{3}$, or a
green $P_{3}$. So, every color must appear in the $K_{4}$. Denote the vertex
set for the $K_{4}$ by $\\{a,b,c,d\\}$ and assume that $ab$ is blue. If $cd$
is red or green, then no other blue edges exist in the $K_{4}$ without forming
a blue $P_{3}$. Since

$r(P_{4},P_{3})=4\quad\mbox{and}\quad r_{*}(P_{4},P_{3})=2,$

it follows that there exists a red $P_{4}$ or a green $P_{3}$. Hence, $cd$
must be blue. If any three of the edges $ac$, $ad$, $bc$, and $bd$ are red,
then they form a red $P_{4}$ (e.g., if $ac$, $ad$, and $bc$ are red, then
$bcad$ is a red $P_{4}$). So, exactly two of these edges must be green and
they must be disjoint. Without loss of generality, assume that $ac$ and $bd$
are green and $ad$ and $bc$ are red. Now introduce vertex $v$, joining it to
the $K_{4}$ with three edges. If any such edge is blue or green, then a blue
or green $P_{3}$ is formed. So, all three edges joining $v$ to the $K_{4}$ are
red, and since one such edge must join $v$ to $\\{a,d\\}$ and one must join
$v$ to $\\{b,c\\}$, we obtain a red $P_{4}$ (e.g., if $va$ and $vb$ are red,
then $davb$ is a red $P_{4}$). It follows that $r_{*}(P_{4},P_{3})\leq 3$.

Case 3 Assume that $k=5$ so that by Equation (4), $r(P_{5},P_{3},P_{3})=5$.
Then the $3$-coloring of $K_{4}\sqcup K_{1,3}$ given in Figure 5 implies that
$r_{*}(P_{5},P_{3},P_{3})=4$.

Figure 5. A $3$-coloring of $K_{4}\sqcup K_{1,3}$ that avoids a red $P_{5}$, a
blue $P_{3}$, and a green $P_{3}$.

Case 4 Assume that $k=6$ so that by Equation (4), $r(P_{6},P_{3},P_{3})=6$.
Inequality (5) implies that $r_{*}(P_{6},P_{3},P_{3})\geq 3$. Consider a
$3$-colored $K_{5}\sqcup K_{1,3}$ (using red, blue, and green) that avoids a
blue $P_{3}$ and a green $P_{3}$. Let $v$ be the center vertex of the star and
$H$ be the underlying $K_{5}$ subgraph. Since $r(P_{5},P_{3},P_{3})=5$ by
Equation (4), $H$ contains a red $P_{5}$. If all the edges incident with $v$
are red, then there exists a red $P_{6}$. As we are to avoid a blue $P_{3}$
and a green $P_{3}$, at least one edge adjacent to $v$ must be red. If $H$ has
at most one blue edge, then $r(C_{5},P_{3})=5$ and $r_{\ast}(C_{5},P_{3})=3$
(from [7] and Theorem 14) imply that $H$ must contain a red $C_{5}$ (assume it
is given by $x_{1}x_{2}x_{3}x_{4}x_{5}x_{1}$). As $v$ is joined to the $K_{5}$
subgraph by at least one red edge, without loss of generality let $vx_{1}$ be
red. Then $vx_{1}x_{2}x_{3}x_{4}x_{5}$ is a red $P_{6}$. This implies that all
colors are present in the $K_{5}\sqcup K_{1,3}$ and the blue and the green
subgraphs of $H$ are both matchings of size $2$. Hence, we consider two
subcases where the subgraph of $H$ spanned by the green and blue edges has
order $4$ or $5$, as shown in Figure 6.

Figure 6. Two critical colorings for $r(P_{6},P_{3},P_{3})$ corresponding to
Case 4 in the proof of Theorem 15.

Subcase 4.1 Suppose that the subgraph of $H$ spanned by the blue and green
edges has order $4$. Up to isomorphism, $H$ must be colored as in the first
image in Figure 6, with the vertices labelled by $a,b,c,d,e$, as shown. Since
$v$ joins to $H$ with three edges, at least two of those edges must join to
the vertices in $\\{b,c,d,e\\}$. Without loss of generality, these edges are
$(vb,vc)$ or $(vb,vd)$. If either of these edges are blue (resp. green) then a
blue (resp. green) $P_{3}$ is formed, so these must be red. If these edges are
$vb$ and $vc$ (resp. $vb$ and $vd$), then $adbvce$ (resp. $ceabvd$) is a red
$P_{6}$.

Subcase 4.2 Suppose that the subgraph of $H$ spanned by the blue and green
edges has order $5$. Up to isomorphism, $H$ must be colored as in the second
image in Figure 6. Note that $cadbec$ is a red $C_{5}$. Since $v$ joins to $H$
with at least one red edge, without loss of generality assume this to be $va$
or $vc$. Then either $vadbec$, or $vcadbe$ is a red $P_{6}$.

Case 5 Assume that $k\geq 7$ so that $r(P_{k},P_{3},P_{3})=k$. Inequality (5)
implies that $r_{*}(P_{k},P_{3},P_{3})\geq 3$. Now consider a red-blue-green
coloring of $K_{k-1}\sqcup K_{1,3}$ and let $v$ be the center vertex of the
missing star. Since $r(C_{k-1},P_{3},P_{3})=k-1$ (see [6]), if the subgraph
$K_{k-1}$ avoids a blue $P_{3}$ and a green $P_{3}$, then it must contain a
red $C_{k-1}$ (assume it is given by the vertices
$a_{1},a_{2},\dots,a_{k-1},a_{1}$ in this order). Since $v$ joins to the
$K_{k-1}$ via three edges, at least one such edge must be red if a blue
$P_{3}$ and a green $P_{3}$ are avoided. Without loss of generality, assume
that $va_{1}$ is red. Then $va_{1}a_{2}\cdots a_{k-1}$ is a red $P_{k}$. ∎

##  5\. Conclusion

In the beginning of Section 4, it was noted that $(P_{m},P_{3})$ is
$P_{3}$-good for all $m\geq 5$. This observation, along with the known values
$r(P_{m},P_{3},P_{3})=m=r(P_{m},P_{3})$ and $r_{*}(P_{m},P_{3})=2$, for all
$m\geq 5$, allow us to apply Theorem 8 to obtain the lower bound
$r_{*}(P_{m},P_{3},P_{3})\geq 2$. Of course, we saw in the previous section
that Theorem 12 offers the improved lower bound $r_{*}(P_{m},P_{3},P_{3})\geq
3$. What other multicolor star-critical Ramsey numbers have improved lower
bounds from using Theorem 12?

## References

  * [1] J. Arste, K. Klamroth, and I. Mengersen, Three Color Ramsey Numbers for Small Graphs, Util. Math. 49 (1996), 85-96.
  * [2] M. Budden, Star-Critical Ramsey Numbers for Graphs, SpringerBriefs in Mathematics, Springer, Cham, 2023.
  * [3] M. Budden and E. DeJonge, Multicolor Star-Critical Ramsey Numbers and Ramsey-Good Graphs, Electron. J. Graph Theory Appl. 10 (2022), 51-66.
  * [4] S. Burr, Ramsey Numbers Involving Graphs with Long Suspended Paths, J. London Math. Soc. (2) 24 (1981), 405-413.
  * [5] V. Chvátal and F. Harary, Generalized Ramsey Theory for Graphs III, Small Off-diagonal Numbers, Pacific J. Math. 41 (1972), 335-345.
  * [6] T. Dzido, Multicolor Ramsey Numbers for Paths and Cycles, Discuss. Math. Graph Theory 25 (2005), 57-65.
  * [7] R. J. Faudree, S. L. Lawrence, T. D. Parsons and R. H. Schelp, Path-Cycle Ramsey Numbers, Discrete Math. 10 (1974) 269-277.
  * [8] L. Gerencsér and A. Gyárfás, On Ramsey-Type Problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967), 167-170.
  * [9] Y. Hao and Q. Lin, Ramsey Number of $K_{3}$ Versus $F_{3,n}$, Discrete Appl. Math. 251 (2018), 345-348.
  * [10] Y. Hao and Q. Lin, Star-Critical Ramsey Numbers for Large Generalized Fans and Books, Discrete Math. 341 (2018), 3385-3393.
  * [11] F. Harary, Graph Theory, Addison-Wesley Publishing Company, Inc., 1969.
  * [12] L. Gerencsér and A. Gyárfás, On Ramsey-Type Problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967), 167-170.
  * [13] J. Hook, The Classification of Critical Graphs and Star-Critical Ramsey Numbers, Ph.D. Dissertation, Lehigh University, 2010.
  * [14] J. Hook, Critical Graphs for $R(P_{n},P_{m})$ and the Star-Critical Ramsey number for paths, Discuss. Math. Graph Theory 35 (2015), 689-701.
  * [15] Y. S. Khobragade, Lower Bounds for Multicolor Star-Critical Ramsey Numbers, Masters Thesis, Indian Institute of Science Education and Research Bhopal, Bhopal, India, 2024.
  * [16] L. Maherani, G. Omidi, G. Raeisi, and M. Shahsiah, On Three-Color Ramsey Number of Paths, Graphs Combin. 31 (2015), 2299-2308.
  * [17] T.D. Parsons, Path-Star Ramsey Numbers, J. Combin. Theory Ser. B 17 (1974), 51-58.
  * [18] S. Radziszowski, Small Ramsey Numbers - Revision 17, Electron. J. Combin. DS1.17 (2024), 133 pages.
  * [19] Y. Zhang, H. Broersma, and Y. Chen, On Star-Critical and Upper Size Ramsey Numbers, Discrete Appl. Math. 202 (2016), 174-180.