# Rainbow independent sets in graphs with maximum degree two ††thanks: The
work was supported by NNSF of China (No. 12071453) and Anhui Initiative in
Quantum Information Technologies (AHY150200) and National Key Research and
Development Project (SQ2020YFA070080).

Yue Maa, Xinmin Houa,b, Jun Gaoa, Boyuan Liua, Zhi Yina
aSchool of Mathematical Sciences
University of Science and Technology of China, Hefei, Anhui 230026, China.
b CAS Key Laboratory of Wu Wen-Tsun Mathematics
University of Science and Technology of China, Hefei, Anhui 230026, China.
<EMAIL_ADDRESS>
###### Abstract

Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every
$k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $\mathcal{D}(2)$
be the family of all graphs with maximum degree at most two. Aharoni et al.
(2019) conjectured that (i) $f_{G}(n,n-1)=n-1$ for all graphs
$G\in\mathcal{D}(2)$ and (ii) $f_{C_{t}}(n,n)=n$ for $t\geq 2n+1$. Lv and Lu
(2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article,
we show that the conjecture (ii) holds for
$t\geq\frac{1}{3}n^{2}+\frac{44}{9}n$. Let $C_{t}$ be a cycle of length $t$
with vertices being arranged in a clockwise order. An ordered set
$I=(a_{1},a_{2},\ldots,a_{n})$ on $C_{t}$ is called a $2$-jump independent
$n$-set of $C_{t}$ if $a_{i+1}-a_{i}=2\pmod{t}$ for any $1\leq i\leq n-1$. We
also show that a collection of 2-jump independent $n$-sets $\mathcal{F}$ of
$C_{t}$ with $|\mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii)
holds if we restrict $\mathcal{F}$ on the family of 2-jump independent
$n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds
for all graphs $G\in\mathcal{D}(2)$ with $c_{e}(G)\leq 4$, where $c_{e}(G)$ is
the number of components of $G$ isomorphic to cycles of even lengths.

##  1 Introduction

Let $\mathcal{F}=(F_{1},F_{2},...,F_{n})$ be a collection of sets (not
necessarily distinct), a (partial) rainbow set of $\mathcal{F}$ is a set
$R=\\{x_{i_{1}},x_{i_{2}},...,x_{i_{m}}\\}$ such that $x_{i_{j}}\in F_{i_{j}}$
for $1\leq i_{1}<i_{2}<\ldots<i_{k}\leq m\leq n$. Given a graph $G$ and a
collection $\mathcal{F}$ of independent sets of $G$, a rainbow set $R$ of
$\mathcal{F}$ is called a rainbow independent set of $(\mathcal{F},G)$ if $R$
is also an independent set of $G$. An $m$-set is a set of size $m$. Let
$\mathcal{I}$ be a family of sets. Write $\mathcal{F}\sqsubseteq\mathcal{I}$
for a collection of sets (not necessarily distinct) $\mathcal{F}$ with each
member of $\mathcal{F}$ belonging to $\mathcal{I}$. Given a graph $G$ and an
integer $n$, write $\mathcal{I}(G)$ (resp. $\mathcal{I}_{n}(G)$ or
$\mathcal{I}_{n^{+}}(G)$) for the family of independent sets (resp.
independent sets such that each of them has uniform size $n$ or of size at
least $n$) of $G$. Given a graph $G$ and integers $m,n$ with $m\leq n$, define

$f_{G}(n,m)=\min\\{|\mathcal{F}|:\mathcal{F}\sqsubseteq\mathcal{I}_{n}(G)\mbox{
and $(\mathcal{F},G)$ has a rainbow indepent $m$-set}\\}.$

Given a family $\mathcal{G}$ of graphs, let

$f_{\mathcal{G}}(n,m)=\sup\\{f_{G}(n,m):G\in\mathcal{G}\\}.$

Clearly, a rainbow matching in a graph is a rainbow independent set in its
line graph. Partially motivated by the study of the rainbow matching problem
in graphs (there are fruitful results about the problem, one can refer [1, 2,
4, 5, 6, 7, 8] for more details), Aharoni, Briggs, Kim and Kim studied the
rainbow independent set problem in certain classes of graphs and proposed
several conjectures in [3].

Let $m\leq n$. Clearly,

$\displaystyle f_{G}(n,m)$ $\displaystyle\geq$ $\displaystyle m.$ (1)

Aharoni, et al. [3] conjectured that the lower bound in (1) is tight for
$f_{G}(n,n-1)$ with $\Delta(G)\leq 2$ and $f_{C_{t}}(n,n)$, where $C_{t}$ is a
cycle with $t$ vertices. Write $\mathcal{D}(2)$ for the family of graphs with
maximum degree two.

######  Conjecture 1.1 (Conjecture 2.14 in [3]).

$f_{\mathcal{D}(2)}(n,n-1)=n-1$.

######  Conjecture 1.2 (Conjecture 2.9 in [3]).

If $t\geq 2n+1$, then $f_{C_{t}}(n,n)=n$.

The following proposition can be easily checked (also has been observed in [2,
3, 8]).

######  Proposition 1.

$f_{C_{2n}}(n,n)=2n-1$.

When $t=2n+1$, Conjecture 1.2 was confirmed by Lv and Lu [10].

######  Theorem 1.3 (Theorem 1 in [10]).

$f_{C_{2n+1}}(n,n)=n$.

In this article, we first show that Conjecture 1.1 is true when $G$ is
2-regular and $|V(G)|\in\\{2n-1,2n\\}$ and then we show that Conjecture 1.2
seems stronger than Conjecture 1.1, i.e. Conjecture 1.2 implies Conjecture 1.1
for graphs $G\in\mathcal{D}(2)$ with $c_{e}(G)\leq 4$, where $c_{e}(G)$ is the
number of components of $G$ isomorphic to cycles of even lengths. So we
concentrate our attention on Conjecture 1.2 and prove that this conjecture
holds when $t$ is large. The main results of the article are listed below.

######  Theorem 1.4.

If $G$ is 2-regular with $2n-1\leq|V(G)|\leq 2n$ then $f_{G}(n,n-1)=n-1$.

######  Theorem 1.5.

If $f_{C_{\ell}}(n,n)=n$ for $\ell\geq 2n+1$, then $f_{G}(n,n-1)=n-1$ for all
graphs $G\in\mathcal{D}(2)$ with $c_{e}(G)\leq 4$, provided that
$\mathcal{I}_{n}(G)\not=\emptyset$.

######  Theorem 1.6.

$f_{C_{t}}(n,n)=n$ for $t>\frac{1}{3}n^{2}+\frac{44}{9}n$.

Given integers $a,b$ with $a\leq b$, let $[a,b]=\\{a,a+1,\ldots,b-1,b\\}$, and
write $[b]$ for $[1,b]$ for simplicity. Let $C_{t}$ be a cycle with vertex set
$[a,a+t-1]$ and edge set $\\{a(a+1),\ldots,(a+t-2)(a+t-1),(a+t-1)a\\}$. For
$t\geq 2n+1$ and $2\leq k\leq t-2$, an ordered set
$I=(a_{1},a_{2},\ldots,a_{n})$ is called a $k$-jump independent set of $C_{t}$
if $a_{i+1}-a_{i}=k\pmod{t}$ for any $1\leq i\leq n-1$. We call $a_{1}$ the
start of $I$, denoted by $s(I)$, and $a_{n}$ the end of $I$. Let
$\mathcal{I}^{k}_{n}(G)$ be the family of all $k$-jump independent $n$-sets in
$G$. We prove that Conjecture 1.2 is true if we restrict
$\mathcal{F}\sqsubseteq\mathcal{I}^{2}_{n}(C_{t})$.

######  Theorem 1.7.

Given integers $t,n$ with $t\geq 2n+1$, if
$\mathcal{F}\subseteq\mathcal{I}^{2}_{n}(C_{t})$ with $|\mathcal{F}|=n$, then
$\mathcal{F}$ has a rainbow independent $n$-set.

Remark: Any independent $n$-set of $C_{2n+1}$ must be a 2-jump set. So the
theorem can be viewed as a generalization of Theorem 1.3 in some sense.

We give a bit more definitions and notation. For a collection $\mathcal{F}$ of
sets and a given set $A$, denote $\mathcal{F}-A=\\{I-A:I\in\mathcal{F}\\}$ and
$\mathcal{F}\cap A=\\{I\cap A:I\in\mathcal{F}\\}$. For a set $B$ of numbers
and a given number $i$, let $B+i=\\{b+i:b\in B\\}$. For a graph $G$ and a
collection $\mathcal{F}$ of independent sets in $G$, let $v\in V(G)$, define
$C_{\mathcal{F}}(v)=\\{I:v\in I\in\mathcal{F}\\}$ to be the list of $v$ and
$c_{\mathcal{F}}(v)=|C_{\mathcal{F}}(v)|$ the list number of $v$. For a
rainbow independent set $R$ of $\mathcal{F}$ and $v\in R$, let $C_{R}(v)$ be
the color (i.e. the independent set in the list $C_{\mathcal{F}}(v)$) assigned
to $v$ and let $C_{R}=\cup_{v\in R}\\{C_{R}(v)\\}$.

The rest of the paper is arranged as follows. We give a greedy algorithm to
find a rainbow independent set for a given graph $G$ and
$\mathcal{F}\sqsubseteq\mathcal{I}(G)$ and some preliminaries in Section 2. We
prove Theorems 1.4 and 1.5 in Section 3. In Sections 4 and 5, we give the
proofs of Theorem 1.6 and 1.7. We also give some discussions in the last
section.

##  2 A greedy algorithm and some preliminaries

First, we give a greedy algorithm (GRIS) to find a rainbow independent set in
a given graph $G$ and $\mathcal{F}\sqsubseteq\mathcal{I}(G)$.

Input: A graph $G$ with ordered vertex set $A=\\{a_{1},a_{2},\ldots,a_{t}\\}$,
and a collection of independent set
$\mathcal{F}=(I_{1},...,I_{k})\sqsubseteq\mathcal{I}(G)$

Output: A rainbow independent set $R$ of $\mathcal{F}$

1

2Set $R=C=\emptyset$ and $j=0$.

3Reset $j:=j+1$. If $C_{\mathcal{F}}(a_{j})\setminus C=\emptyset$ or
$C_{\mathcal{F}}(a_{j})\setminus C\neq\emptyset$ but $R\cup\\{a_{j}\\}$ is not
an independent set, go to step 3; otherwise, reset $R:=R\cup\\{a_{j}\\}$ and
choose $I_{i}\in C_{\mathcal{F}}(a_{j})\backslash C$ with the minimal index
$i$ and reset $C:=C\cup\\{I_{i}\\}$.

4If $j<t$, return to step 2; else if $j=t$, then stop and output
$R=\mbox{GRIS}(G,\mathcal{F})$ and $C=C(G,\mathcal{F})$. We call
$C(G,\mathcal{F})$ a greedy color set.

Algorithm 2.1 GREEDY-RAINBOW-INDEPENDENT-SET (GRIS($G,\mathcal{F})$)

It is easy to check that the output $R=\mbox{GRIS}(G,\mathcal{F})$ is a
rainbow independent set of $(\mathcal{F},G)$. The following is a simple fact
when we apply GRIS to a path.

######  Lemma 2.1.

Let $P_{t}$ be a path with vertex set $[t]$ and edge set
$\\{12,23,\ldots,(t-1)t\\}$ and
$\mathcal{F}\sqsubseteq\mathcal{I}_{(n-1)^{+}}(P_{t})$ with $|\mathcal{F}|\geq
n-1$. Suppose $t\geq 2n-1$. Let $R=\mbox{GRIS}(P_{t},\mathcal{F})$ and
$C=C(P_{t},\mathcal{F})$. If $|R|<n$, then $|R|=n-1$ and, for any
$I\in\mathcal{F}\backslash C$, we have $|I|=n-1$ and $|I\cap\\{a,a+1\\}|=1$
for any $a\in R$.

###### Proof.

Suppose $|R|=|C|=k<n$. Pick $I\in\mathcal{F}\setminus C$. Then, for any $i\in
I$, $R\cup\\{i\\}$ can not be a larger independent set of $P_{t}$. Thus $i\in
R$ or $i$ is a neighbor of some vertex in $R$, i.e. $i\in(R-1)\cup
R\cup(R+1)$. If $i\notin R\cup(R+1)$, then $i\in R-1$, i.e., $i+1\in R$. But
at step $i$ of the algorithm GRIS, $i$ will be added to $R$ since $i-1\notin
R$. This is a contradiction to $i+1\in R$. Hence $i\in R\cup(R+1)$. Since $I$
is an independent set, $|I\cap\\{a,a+1\\}|\leq 1$ for any $a\in R$. So
$n-1\leq|I|\leq|R|=k<n$. Thus we have $|I|=|R|=k=n-1$ and
$|I\cap\\{a,a+1\\}|=1$ for any $a\in R$. ∎

In Lemma 2.1, if we choose $\mathcal{F}\in\mathcal{I}_{n}(P_{t})$ with
$|\mathcal{F}|=n$ then $|R|$ must be $n$. So we have the following corollary.

######  Corollary 2.2.

Suppose $t\geq 2n-1$. Then $f_{P_{t}}(n,n)=n$.

Remark: Note that Aharoni et al. have proved that for the family of chordal
graphs $\mathcal{T}$ and $m\leq n$, $f_{\mathcal{T}}(n,m)=m$ (Theorem 3.20 in
[3]). So, in fact, we have the following result.

######  Corollary 2.3.

Suppose $t\geq 2n-1$ and $F_{t}$ is a forest of order $t$. Then
$f_{F_{t}}(n,m)=m$ for $m\leq n$.

######  Corollary 2.4.

Let $C_{t}$ be a cycle with vertex set $[t]$ and edge set
$\\{12,23,\ldots,(t-1)t,t1\\}$. Suppose $t\geq 2n$. Then we have

(A) $f_{C_{t}}(n,n-1)=n-1$.

(B) Let $m$ be the maximum integer such that $f_{C_{t}}(n,m)=n$. Then $m\geq
n-1$. Suppose $\mathcal{F}\sqsubseteq\mathcal{I}_{n}(C_{t})$ with
$|\mathcal{F}|=n$. If $m=n-1$ then the following hold.

(B1) $c_{\mathcal{F}}(i)>0$ for any $i\in[t]$.

(B2) If $C_{\mathcal{F}}(i)=I$ for some $i\in[t]$, then $I\in
C_{\mathcal{F}}(i\pm 2)$.

(B3) If $c_{\mathcal{F}}(i)=1$ for some $i\in[t]$ and $t\geq 2n+1$, then
$c_{\mathcal{F}}(i\pm 1)>1$.

###### Proof.

Suppose $\mathcal{F}\sqsubseteq\mathcal{I}_{n}(C_{t})$ with $|\mathcal{F}|=k$.
Let $P_{t-1}=C_{t}-\\{t\\}$ and $\mathcal{F}^{\prime}=\mathcal{F}-\\{t\\}$.
Then $\mathcal{F}^{\prime}\sqsubseteq\mathcal{I}_{(n-1)^{+}}(P_{t-1})$. Note
that $t-1\geq 2n-1$. We can apply the algorithm GRIS to $P_{t-1}$ and
$\mathcal{F}^{\prime}$. Let $R=\mbox{GRIS}(P_{t-1},\mathcal{F}^{\prime})$.
Then $|R|\leq|\mathcal{F}^{\prime}|=k$.

(A) If $k=n-1$ then $|R|\leq k<n$. By Lemma 2.1, $|R|=n-1$. Clearly, $R$ is a
rainbow independent set of $(\mathcal{F},C_{t})$ too. This implies that
$f_{C_{t}}(n,n-1)=n-1$.

(B) Suppose $k=n$. Then $|R|\leq k=n$. If $|R|<n$, by Lemma 2.1, we have
$|R|=n-1$. So we have $m\geq|R|\geq n-1$. Now we assume $m=n-1$.

(B1) If there is a vertex $i\in[t]$ with $c_{\mathcal{F}}(i)=0$, without loss
of generality, assume $i=t$, then
$\mathcal{F}^{\prime}=\mathcal{F}-\\{t\\}=\mathcal{F}\sqsubseteq\mathcal{I}_{n}(P_{t-1})$.
Note that $t-1\geq 2n-1$. By Corollary 2.2, we can find a rainbow independent
$n$-set $R^{\prime}$ of $(\mathcal{F}^{\prime},P_{t-1})$, which is also a
rainbow independent $n$-set of $(\mathcal{F},C_{t})$, a contradiction to the
maximality of $m$.

(B2) Without loss of generality, assume $C_{\mathcal{F}}(t)=\\{I\\}$. By the
symmetry of $C_{t}$, it is sufficient to prove $2\in I$. Recall that
$\mathcal{F}^{\prime}=\mathcal{F}-\\{t\\}\sqsubseteq\mathcal{I}_{(n-1)^{+}}(P_{t-1})$.
Let $C=C(P_{t-1},\mathcal{F}^{\prime})$. Note that
$m=|R|=|\mbox{GRIS}(P_{t-1},\mathcal{F}^{\prime})|=|C|=n-1$ and
$|\mathcal{F}^{\prime}|=n$. We have $|\mathcal{F}^{\prime}\setminus C|=1$. Let
$\mathcal{F}^{\prime}\setminus C=\\{I^{\prime}\\}$. By Lemma 2.1, we have
$|I^{\prime}|=n-1$ and $|I^{\prime}\cap\\{a,a+1\\}|=1$ for every $a\in R$.
Since $I$ is the only independent set containing $t$ in $\mathcal{F}$, we have
$I^{\prime}=I\setminus\\{t\\}$. By (B1),
$C_{\mathcal{F}^{\prime}}(1)=C_{\mathcal{F}}(1)\neq\emptyset$. So by the
processing of the algorithm GRIS, $1$ is the first vertex added to $R$. Hence
$|(I\setminus\\{t\\})\cap\\{1,2\\}|=1$. Since $1t\in E(C_{t})$ and $t\in I$,
we have $1\notin I$. This implies that $2\in I$.

(B3) If not, there are two consecutive vertices $i,i+1\in[t]$ with
$|C_{\mathcal{F}}(i)|=|C_{\mathcal{F}}(i+1)|=1$. Without loss of generality,
assume $i=t-3$ and $C_{\mathcal{F}}(t-3)=\\{I_{1}\\}$ and
$C_{\mathcal{F}}(t-2)=\\{I_{2}\\}$. Let $P_{t-6}=C_{t}-[t-5,t]$ and
$\mathcal{F}^{\prime}=(\mathcal{F}\setminus\\{I_{1},I_{2}\\})-[t-5,t]$. Since
$I_{1}$ is the only member of $\mathcal{F}$ containing $t-3$ and $I_{2}$ is
the only one of $\mathcal{F}$ containing $t-2$, we have
$I\cap\\{t-3,t-2\\}=\emptyset$ for any
$I\in\mathcal{F}\setminus\\{I_{1},I_{2}\\}$. So $|I\cap[t-5,t]|\leq 2$ for any
$I\in\mathcal{F}\setminus\\{I_{1},I_{2}\\}$. Thus
$\mathcal{F}^{\prime}\sqsubseteq\mathcal{I}_{(n-2)^{+}}(P_{t-6})$. Note that
$t-6\geq 2n+1-6=2(n-2)-1$. By Corollary 2.2, we have
$f_{P_{t-6}}(n-2,n-2)=n-2$. So we have a rainbow independent $(n-2)$-set $R$
of $(P_{t-6},\mathcal{F}^{\prime})$. This is also a rainbow independent
$(n-2)$-set of $(\mathcal{F}\setminus\\{I_{1},I_{2}\\},C_{t})$. Recall that
$C_{\mathcal{F}}(t-3)=\\{I_{1}\\}$ and $C_{\mathcal{F}}(t-2)=\\{I_{2}\\}$. By
(B2), $I_{1}\in C_{\mathcal{F}}(t-1)$ and $I_{2}\in C_{\mathcal{F}}(t-4)$.
Therefore, by adding $t-4$ and $t-1$ to $R$, we get a rainbow independent
$n$-set $R\cup\\{t-1,t-4\\}$ of $(\mathcal{F},C_{t})$, a contradiction to
$m=n-1$.

∎

##  3 Proofs of Theorem 1.4 and 1.5

An odd (resp. even) cycle is a cycle of odd length (resp. even length).

###### Proof of Theorem 1.4.

We prove by induction on the number of components $c(G)$ of $G$. If $c(G)=1$,
then $G$ is a cycle. By Corollaries 2.4 (A), we have $f_{G}(n,n-1)=n-1$. Now
suppose $c(G)>1$ and the result holds for all 2-regular graphs $H$ with
$c(H)<c(G)$. Let
$\mathcal{F}=(I_{1},I_{2},\ldots,I_{n-1})\sqsubseteq\mathcal{I}_{n}(G)$.

If $G$ has a component isomorphic to a cycle $C_{2m+1}$ for some $m\in[n-1]$,
then $|I_{i}\cap V(C_{2m+1})|=m$ for every $i\in[n-1]$ because
$2n-1\leq|V(G)|\leq 2n$. Let $\mathcal{F}_{1}=(I_{1}\cap
V(C_{2m+1}),\ldots,I_{m}\cap V(C_{2m+1}))$. Then
$\mathcal{F}_{1}\sqsubseteq\mathcal{I}_{m}(C_{2m+1})$. By Theorem 1.3, we can
find a rainbow independent $m$-set $R_{1}$ of $(\mathcal{F}_{1},C_{2m+1})$.
Let $H=G-V(C_{2m+1})$ and $\mathcal{F}_{2}=(I_{m+1}\cap
V(H),\ldots,I_{n-1}\cap V(H))$. Then $H$ is 2-regular with $|V(H)|=2(n-m)-1$
and $\mathcal{F}_{2}\sqsubseteq\mathcal{I}_{n-m}(H)$. By the induction
hypothesis, there is a rainbow independent $(n-m-1)$-set $R_{2}$ of
$(\mathcal{F}_{2},H)$. So $R_{1}\cup R_{2}$ is a rainbow independent
$(n-1)$-set of $(\mathcal{F},G)$, we are done.

Now suppose that every component of $G$ is an even cycle. Let $G=C_{1}\cup
C_{2}\cup\ldots\cup C_{k}$ with $|V(C_{i})|=2n_{i}$ for $i\in[k]$. Then
$|I_{i}\cap V(C_{j})|=n_{j}$ for every $i\in[n-1]$ and $j\in[k]$. Let
$H=C_{2}\cup\ldots\cup C_{k}$. Then $\mathcal{F}^{\prime}=(I_{n_{1}+1}\cap
V(H),\ldots,I_{n-1}\cap V(H))\sqsubseteq\mathcal{I}_{n-n_{1}}(H)$. By the
induction hypothesis, there is a rainbow independent $(n-n_{1}-1)$-set
$R^{\prime}$ of $(\mathcal{F}^{\prime},H)$. So $|R^{\prime}\cap
V(C_{j})|=n_{j}$ for all $j\in[2,k]$ but exactly one exception, without loss
of generality, say $C_{2}$, with $|R^{\prime}\cap V(C_{2})|=n_{2}-1$. Let
$J=\cup_{v\in R^{\prime}\cap V(C_{2})}C_{R^{\prime}}(v)$. Then $|J|=n_{2}-1$.
Let $\mathcal{F}_{1}=(I_{j}:j\in[n_{1}]\text{ or }I_{j}\in J)$ and assume
$n_{1}\leq n_{2}$. Then $|\mathcal{F}_{1}|=n_{1}+n_{2}-1\geq 2n_{1}-1$ and
$\mathcal{F}_{1}\cap V(C_{1})\sqsubseteq\mathcal{I}_{n_{1}}(C_{1})$. So we
have a rainbow independent $n_{1}$-set $R_{1}$ of $(\mathcal{F}_{1}\cap
V(C_{1}),C_{1})$ by Proposition 1. Let
$\mathcal{F}_{2}=\mathcal{F}_{1}\setminus C_{R_{1}}$. Then
$|\mathcal{F}_{2}|=n_{2}-1$ and $\mathcal{F}_{2}\cap
V(C_{2})\sqsubseteq\mathcal{I}_{n_{2}}(C_{2})$. By Corollary 2.4 (A), there is
a rainbow independent $(n_{2}-1)$-set of $(\mathcal{F}_{2}\cap
V(C_{2}),C_{2})$. Therefore, $R^{\prime}\setminus(R^{\prime}\cap V(C_{2}))\cup
R_{1}\cup R_{2}$ is rainbow independent $(n-1)$-set of $(\mathcal{F},G)$. This
completes the proof. ∎

Let $V$ be a finite set and $\mathcal{I}\sqsubseteq 2^{V}$. For a subset
$S\subset V$, define

$h(\mathcal{I},S)=\max\\{m:|\\{I\in\mathcal{I}:|I\cap S|\geq m\\}|\geq m\\}.$

######  Lemma 3.1.

Let $W$ be a finite set and $V\subseteq W$. Suppose $\mathcal{I}\sqsubseteq
2^{W}$ is a collection of $n^{+}$-sets with $|\mathcal{I}|=n$ and
$h(\mathcal{I},V)=n$. Let $(V_{1},V_{2})$ be a partition of $V$ and let
$h(\mathcal{I},V_{i})=m_{i}$ for $i=1,2$. Then we have $m_{1}+m_{2}\geq n$.
Furthermore,

(i) for each $\ell\leq m_{1}+m_{2}-n$, there exists a partition
$(\mathcal{I}_{1},\mathcal{I}_{2})$ of $\mathcal{I}$ such that
$h(\mathcal{I}_{1},V_{1})=m_{1}-\ell$ and
$h(\mathcal{I}_{2},V_{2})=n-m_{1}+\ell$;

(ii) if $m_{1}+m_{2}-n=0$, then $|I\cap V_{3-i}|\leq m_{3-i}$ for every
$I\in\mathcal{I}_{i}$ and $i=1,2$;

(iii) if $m_{1}+m_{2}-n>0$ and $\ell\leq m_{1}+m_{2}-n-1$, then we can choose
$\mathcal{I}_{2}$ with $|I\cap V_{2}|\geq n-m_{1}+\ell+1$ for every
$I\in\mathcal{I}_{2}$.

###### Proof.

Assume $\mathcal{I}=(I_{1},I_{2},\ldots,I_{n})$ with $|I_{1}\cap
V_{1}|\geq|I_{2}\cap V_{1}|\geq\ldots\geq|I_{n}\cap V_{1}|$. By the definition
of $m_{1}$, $|I_{i}\cap V_{1}|\geq m_{1}$ for each $1\leq i\leq m_{1}$ and
$|I_{j}\cap V_{1}|\leq m_{1}$ for each $m_{1}+1\leq j\leq n$. So we have
$|I_{j}\cap V_{2}|\geq n-m_{1}$ for each $m_{1}+1\leq j\leq n$. By the
definition of $m_{2}$, we have $m_{2}\geq n-m_{1}$, i.e. $m_{1}+m_{2}\geq n$.

(i) Let $\ell\leq m_{1}+m_{2}-n$ and
$\mathcal{I}_{1}^{\prime}=\\{I_{i}:|I_{i}\cap V_{1}|\geq m_{1}-\ell\\}$ and
$\mathcal{I}_{2}^{\prime}=\\{I_{i}:|I_{i}\cap V_{2}|\geq n-m_{1}+\ell\\}$. By
the definition of $m_{1}$ and $m_{2}$, we have $|\mathcal{I}_{1}^{\prime}|\geq
m_{1}$ and $|\mathcal{I}_{2}^{\prime}|\geq m_{2}$. Since every $|I_{i}|\geq
n$, we have either $|I_{i}\cap V_{1}|\geq m_{1}-\ell$ or $|I_{i}\cap
V_{2}|>n-m_{1}+\ell$. Hence
$\mathcal{I}_{1}^{\prime}\cup\mathcal{I}_{2}^{\prime}=\mathcal{I}$ and so
$|\mathcal{I}_{1}^{\prime}\setminus\mathcal{I}_{2}^{\prime}|\leq n-m_{2}\leq
m_{1}-\ell$. Therefore, we can choose a subset $\mathcal{I}_{1}$ of
$\mathcal{I}$ with
$\mathcal{I}_{1}^{\prime}\setminus\mathcal{I}_{2}^{\prime}\subseteq\mathcal{I}_{1}\subseteq\mathcal{I}_{1}^{\prime}$
and $|\mathcal{I}_{1}|=m_{1}-\ell$. Let
$\mathcal{I}_{2}=\mathcal{I}\setminus\mathcal{I}_{1}$. Clearly,
$h(\mathcal{I}_{1},V_{1})=m_{1}-\ell$ and
$h(\mathcal{I}_{2},V_{2})=n-m_{1}+\ell$.

(ii) Clearly, if $\ell=m_{1}+m_{2}-n=0$ then $|I\cap V_{3-i}|\leq
n-m_{i}=m_{3-i}$ for any $I\in\mathcal{I}_{i}$ and $i=1,2$.

(iii) If $m_{1}+m_{2}-n>0$ and $\ell\leq m_{1}+m_{2}-n-1$, then we can reset
$\mathcal{I}_{2}^{\prime}=\\{I_{i}:|I_{i}\cap V_{2}|\geq n-m_{1}+\ell+1\\}$.
Note that $n-m_{1}+\ell+1\leq m_{2}$. All discussions in (i) keep true. Thus,
we have the desired partition $(\mathcal{I}_{1},\mathcal{I}_{2})$ of
$\mathcal{I}$ with $|I\cap V_{2}|\geq n-m_{1}+\ell+1$ for every
$I\in\mathcal{I}_{2}$. ∎

Now we give the proof of Theorem 1.5.

###### Proof of Theorem 1.5:.

Suppose to the contrary that there is a graph $G\in\mathcal{D}(2)$ with
$c_{e}(G)\leq 4$ and an
$\mathcal{F}=(I_{1},I_{2},\ldots,I_{n-1})\sqsubseteq\mathcal{I}_{n}(G)$ such
that $G$ contains no rainbow independent $(n-1)$-set of $(\mathcal{F},G)$.
Since $G\in\mathcal{D}(2)$, each component of $G$ is a path or a cycle. Assume
that $G$ is a minimum counterexample. We claim that $G$ contains no component
isomorphic to a path or an odd cycle.

######  Claim 1.

$G$ contains no component $H$ with $f_{H}(h,h)=h$, where
$h=h(\mathcal{F},V(H))$. In particular, $G$ contains no component isomorphic
to a path or an odd cycle.

###### Proof.

Suppose to the contrary that there is a component $H$ of $G$ with
$f_{H}(h,h)=h$, where $h=f(\mathcal{F},V(H))$. Let $G^{\prime}=G-V(H)$.
Without loss of generality, assume $|I_{1}\cap V(H)|\geq|I_{2}\cap
V(H)|\geq\ldots\geq|I_{n-1}\cap V(H)|$. So $|I_{i}\cap V(H)|\geq h$ for every
$1\leq i\leq h$ and $|I_{j}\cap V(G^{\prime})|\leq h$ for every $h+1\leq j\leq
n-1$ by the definition of $h$. Let $\mathcal{F}_{1}=(I_{1},\ldots,I_{h})$ and
$\mathcal{F}_{2}=(I_{h+1},\ldots,I_{n-1})$. Then
$\mathcal{F}_{1}\sqsubseteq\mathcal{I}_{h^{+}}(H)$ and
$\mathcal{F}_{2}\sqsubseteq\mathcal{I}_{(n-h)^{+}}(G^{\prime})$. Since
$f_{H}(h,h)=h$, we can find a rainbow independent $h$-set $R_{1}$ of
$(\mathcal{F}_{1},H)$. Since $G$ is a minimum counterexample, we can find a
rainbow independent $(n-h-1)$-set $R_{2}$ of $(\mathcal{F}_{2},G^{\prime})$.
Therefore, $R_{1}\cup R_{2}$ is a rainbow independent $(n-1)$-set of
$(\mathcal{F},G)$, a contradiction.

If $H$ is isomorphic to a path or an odd cycle. Then $|V(H)|\geq 2h+1$ if $H$
is an odd cycle and $2h$ otherwise. By the assumption $f_{C_{s}}(h,h)=h$ when
$s\geq 2h+1$ and Corollary 2.3, we always have $f_{H}(h,h)=h$. We are done.

∎

By Claim 1, we may assume that $G$ consists of $k$ even cycles, namely
$G=\cup_{i=1}^{k}C_{i}$, where $|V(C_{i})|=2n_{i},1\leq i\leq k$. By Corollary
2.4 (A), $k\geq 2$. Let $V_{i}=V(C_{i})$. By Claim 1,
$h(\mathcal{F},V_{i})=n_{i}$ for $i\in[k]$. Let
$\mathcal{F}_{i}=\\{I_{j}\in\mathcal{F}:|I_{j}\cap V_{i}|=n_{i}\\}$,
$i\in[k]$. Then $|\mathcal{F}_{i}|\geq n_{i}$ for $i\in[k]$. Denote
$t=\sum_{i=1}^{k}n_{i}-n$.

######  Claim 2.

$t\geq k-1$.

###### Proof.

Suppose to the contrary that $t\leq k-2$. Note that
$n=|I|=\sum_{i=1}^{k}|I\cap V_{i}|$ for every $I\in\mathcal{F}$. So there are
at least two cycles $C_{i},i\in[k]$ with $|I\cap V_{i}|\geq n_{i}$, i.e.,
every $I$ lies in at least two of $\\{\mathcal{F}_{i},i\in[k]\\}$ for every
$I\in\mathcal{F}$. Therefore,

$\sum_{i=1}^{k}|\mathcal{F}_{i}|\geq
2|\mathcal{F}|=2(n-1)=2\sum_{i=1}^{k}n_{i}-2t-2>\sum_{i=1}^{k}(2n_{i}-2).$

Thus there exists at least one $i\in[k]$, say $i=1$, such that
$|\mathcal{F}_{1}|\geq 2n_{1}-1$. By Proposition 1, we can find a rainbow
independent $n_{1}$-set $R_{1}$ of $(\mathcal{F}_{1},C_{1})$. By the
minimality of $G$, we can find a rainbow independent $(n-n_{1}-1)$-set $R_{2}$
of $(\mathcal{F}\setminus C_{R_{1}},G-V_{1})$. Hence $R_{1}\cup R_{2}$ is a
rainbow independent $(n-1)$-set of $(\mathcal{F},G)$, a contradiction. ∎

Let $n_{k}=\min\\{n_{1},\ldots,n_{k}\\}$. By Corollary 2.4 (A), there is a
rainbow independent $(n_{k}-1)$-set $R_{k}$ of $(\mathcal{F}_{k},C_{k})$. Let
$\mathcal{A}=\mathcal{F}\setminus C_{R_{k}}$. Then

$|\mathcal{A}|=n-1-(n_{k}-1)=\sum_{i=1}^{k-1}n_{i}-t$

and

$h(\mathcal{A},G-V_{k})=\sum_{i=1}^{k-1}n_{i}-t$

because $|I\cap V(G-V_{k})|\geq n-n_{k}=\sum_{i=1}^{k-1}n_{i}-t$ for every
$I\in\mathcal{A}$. If $k=2$, then $G-V_{k}=C_{1}$ and so
$h(\mathcal{A},C_{1})=n_{1}-t<n_{1}$ because $t\geq k-1=1$. By the assumption
$f_{C_{s}}(n,n)=n$ for $s\geq 2n+1$, we have a rainbow independent
$(n_{1}-t)$-set $R_{1}$ of $(\mathcal{A},C_{1})$. Hence $R_{1}\cup R_{2}$ is a
rainbow independent $(n-1)$-set of $(\mathcal{F},G)$, a contradiction.

Now assume that $k\geq 3$. Let $\hat{V_{i}}=V(G-V_{k}-V_{i})$ and
$h(\mathcal{A},V_{i})=m_{i}$ for $i\in[k-1]$. Then $\hat{V_{i}}\neq\emptyset$.
Applying Lemma 3.1 to $V_{i}\cup\hat{V_{i}}$, we have
$m_{i}+h(\mathcal{A},\hat{V_{i}})\geq|\mathcal{A}|$.

######  Claim 3.

For $i\in[k-1]$,

$m_{i}+h(\mathcal{A},\hat{V_{i}})=\left\\{\begin{array}[]{ll}|\mathcal{A}|+1&\text{if
$m_{i}=n_{i}$}\\\ |\mathcal{A}|&\text{otherwise.}\end{array}\right.$

###### Proof.

We only prove the case $i=1$ and the other cases can be shown similarly. If
$m_{1}=n_{1}$ and $m_{1}+h(\mathcal{A},\hat{V_{1}})=|\mathcal{A}|$, then by
Lemma 3.1 (i) and (ii), $\mathcal{A}$ can be partitioned into
$\mathcal{A}_{1}\cup\mathcal{A}_{2}$ such that
$h(\mathcal{A}_{1},V_{1})=n_{1}$ and
$h(\mathcal{A}_{1},\hat{V_{1}})=|\mathcal{A}|-n_{1}$, furthermore, for any
$I\in\mathcal{A}_{1},$ we have $|I\cap\hat{V_{1}}|\leq|\mathcal{A}|-n_{1}$.
Thus, for every $I\in\mathcal{A}_{1}$, $|I\cap V_{k}|=|I\cap(V_{1}\cup
V_{k})|-|I\cap V_{1}|\geq n-(|\mathcal{A}|-n_{1})-n_{1}=n_{k}$, i.e.
$\mathcal{A}_{1}\subset\mathcal{F}_{k}$. Hence $|\mathcal{F}_{k}|\geq
2n_{k}-1$. By Proposition 1, we can find a rainbow independent $n_{k}$-set
$R_{k}^{\prime}$ of $(\mathcal{F}_{k},C_{k})$. Let
$\mathcal{F}^{\prime}=\mathcal{F}\setminus C_{R_{k}^{\prime}}$. Then
$|\mathcal{F}^{\prime}|=n-1-n_{k}$ and $|I\cap V(G-V_{k})|\geq n-n_{k}$ for
every $I\in\mathcal{F}^{\prime}$. By the minimality of $G$, there is a rainbow
independent $(n-1-n_{k})$-set $R^{\prime}$ of
$(\mathcal{F}^{\prime},G-V_{k})$. Therefore, $R_{k}^{\prime}\cup R^{\prime}$
is a rainbow independent $(n-1)$-set of $(\mathcal{F},G)$, a contradiction.

Now assume $m_{1}+h(\mathcal{A},\hat{V_{1}})\geq|\mathcal{A}|+2$ if
$m_{1}=n_{1}$, or $m_{1}+h(\mathcal{A},\hat{V_{1}})\geq|\mathcal{A}|+1$ if
$m_{1}<n_{1}$. By applying Lemma 3.1 (i) and (iii) to $V_{1}\cup\hat{V_{1}}$,
we can partition $\mathcal{A}$ into $\mathcal{A}_{1}\cup\mathcal{A}_{2}$ such
that (1) $h(\mathcal{A}_{1},V_{1})=n_{1}-1$,
$h(\mathcal{A}_{2},\hat{V_{1}})=|\mathcal{A}|+1-n_{1}$ and for any
$I\in\mathcal{A}_{2}$, $|I\cap\hat{V_{1}}|\geq|\mathcal{A}|+2-n_{1}$ if
$m_{1}=n_{1}$ (choose $\ell=1$) (which implies that
$|\mathcal{A}_{1}|=n_{1}-1$), or $h(\mathcal{A}_{1},V_{1})=m_{1}$,
$h(\mathcal{A}_{2},\hat{V_{1}})=|\mathcal{A}|-m_{1}$ and for any
$I\in\mathcal{A}_{2}$, $|I\cap\hat{V_{1}}|\geq|\mathcal{A}|+1-m_{1}$ if
$m_{1}<n_{1}$ (choose $\ell=0$) (which implies that
$|\mathcal{A}_{1}|=m_{1}$). By the assumption $f_{C_{s}}(m,m)=m$ for $s\geq
2m+1$, we have a rainbow independent $|\mathcal{A}_{1}|$-set $R_{1}$ of
$(\mathcal{A}_{1},C_{1})$. On the other hand, by the minimality of $G$, we
have a rainbow independent $|\mathcal{A}_{2}|$-set $R_{2}$ of
$(\mathcal{A}_{2},G-V_{k}-V_{1})$. Hence $R_{1}\cup R_{2}\cup R_{k}$ is a
rainbow independent $(n-1)$-set of $(\mathcal{F},G)$, a contradiction too.

∎

If $k=3$, then
$m_{i}+h(\mathcal{A},\hat{V_{i}})=m_{i}+h(\mathcal{A},V_{3-i})=m_{i}+m_{3-i}$
for $i=1,2$. So we have either $m_{i}=n_{i}$ for $i=1,2$ or $m_{i}<n_{i}$ for
$i=1,2$ by Claim 3. For the former case, we have
$n_{1}+n_{2}=m_{1}+m_{2}=|\mathcal{A}|+1=n-n_{3}+1$. So
$t=n_{1}+n_{2}+n_{3}-n=1$, which is a contradiction to $t\geq k-1$. For the
latter case, we have $m_{1}+m_{2}=|\mathcal{A}|=n-n_{3}$. Applying Lemma 3.1
(i) and (ii) to $V_{1}\cup V_{2}$, we can partition $\mathcal{A}$ into
$\mathcal{A}_{1}\cup\mathcal{A}_{2}$ such that
$h(\mathcal{A}_{1},V_{1})=m_{1}<n_{1}$ and
$h(\mathcal{A}_{2},V_{2})=|\mathcal{A}|-m_{1}=m_{2}<n_{2}$. By the assumption
$f_{C_{s}}(m,m)=m$ for $s\geq 2m+1$, we obtain a rainbow independent
$m_{i}$-set $R_{i}$ of $(\mathcal{A}_{i},C_{i})$ for $i=1,2$. Thus $R_{1}\cup
R_{2}\cup R_{3}$ is a rainbow independent $(n-1)$-set of $(\mathcal{F},G)$, a
contradiction.

Now, we assume $k=4$. Hence $t\geq k-1=3$. We distinguish two cases according
to the relations of $m_{i}$ and $n_{i}$ for $i\in[3]$.

If there exists some $i\in[3]$, say $i=3$, such that $m_{3}<n_{3}$. By Claim
3, $|\mathcal{A}|=m_{3}+h(\mathcal{A},V_{1}\cup V_{2})$. First, we claim that
we can choose $\mathcal{A}$ (recall that $\mathcal{A}=\mathcal{F}\setminus
C_{R_{4}}$) with $m_{3}=h(\mathcal{A},V_{3})=n_{3}-1$. To show this, we choose
$C_{R_{4}}$ such that $|\mathcal{F}_{3}\cap\mathcal{A}|$ is as large as
possible. If $|\mathcal{F}_{3}\cap\mathcal{A}|\geq n_{3}-1$, then
$h(\mathcal{A},V_{3})\geq n_{3}-1$, we are done. So, assume
$|\mathcal{F}_{3}\cap\mathcal{A}|<n_{3}-1$. By applying Lemma 3.1 (i) and (ii)
on $V_{3}\cup\hat{V_{3}}$, we can partition $\mathcal{A}$ into
$\mathcal{A}_{3}\cup\mathcal{A}_{3}^{\prime}$ such that
$h(\mathcal{A}_{3},V_{3})=m_{3}$ and $h(\mathcal{A}_{3}^{\prime},V_{1}\cup
V_{2})=n-n_{4}-m_{3}$, moreover, we can choose an
$I_{0}\in\mathcal{A}_{3}^{\prime}$ such that $|I_{0}\cap(V_{1}\cup
V_{2})|=n-n_{4}-m_{3}$ and $|I_{0}\cap V_{3}|\leq m_{3}$. This implies that
$I_{0}\in\mathcal{F}_{4}$ but $I_{0}\notin\mathcal{F}_{3}$. Therefore, reset
$\mathcal{A}$ by replacing $I_{0}$ with some set of $\mathcal{F}_{3}\cap
C_{R_{4}}$, we obtain a new $\mathcal{A}$ with larger
$|\mathcal{F}_{3}\cap\mathcal{A}|$, a contradiction. Now we have
$m_{3}=h(\mathcal{A},V_{3})=n_{3}-1$ and so $h(\mathcal{A},V_{1}\cup
V_{2})=|\mathcal{A}|-m_{3}=n_{1}+n_{2}-t+1$. Again applying Lemma 3.1 (i) and
(ii) to $V_{3}\cup\hat{V_{3}}$, we can partition $\mathcal{A}$ into
$\mathcal{A}_{3}$ and $\mathcal{A}_{3}^{\prime}$ with
$h(\mathcal{A}_{3},V_{3})=n_{3}-1$ and $h(\mathcal{A}_{3}^{\prime},V_{1}\cup
V_{2})=n_{1}+n_{2}-t+1$, furthermore, for any $I\in\mathcal{A}_{3}^{\prime}$,
$|I\cap V_{3}|\leq n_{3}-1$ (this also implies that
$|\mathcal{A}_{3}|=n_{3}-1$ and $|\mathcal{A}_{3}^{\prime}|=n_{1}+n_{2}-t+1$).
By the assumption $f_{C_{s}}(m,m)=m$ for $s\geq 2m+1$, we can find a rainbow
independent $(n_{3}-1)$-sets $R_{3}$ of $(\mathcal{A}_{3},C_{3})$. We claim
that there is at least one of $h(\mathcal{A}_{3}^{\prime},V_{i}),\ i=1,2$ with
$h(\mathcal{A}_{3}^{\prime},V_{i})=n_{i}$. Otherwise, we have
$m_{i}^{\prime}=h(\mathcal{A}_{3}^{\prime},V_{i})<n_{i},\ i=1,2$. Applying
Lemma 3.1 (i) to $V_{1}\cup V_{2}$, we have
$m_{1}^{\prime}+m_{2}^{\prime}\geq|\mathcal{A}_{3}^{\prime}|$ and
$\mathcal{A}_{3}^{\prime}$ can be partitioned into $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$ with $h(\mathcal{B}_{1},V_{1})=m_{1}^{\prime}$ and
$h(\mathcal{B}_{2},V_{2})=|\mathcal{A}_{3}^{\prime}|-m_{1}^{\prime}\leq
m_{2}^{\prime}$ (choose $\ell=0$). By the assumption $f_{C_{s}}(m,m)=m$ for
$s\geq 2m+1$, we have a rainbow independent $m_{1}^{\prime}$-set $R_{1}$ of
$(\mathcal{B}_{1},C_{1})$ and a rainbow independent
$(|\mathcal{A}_{3}^{\prime}|-m_{1}^{\prime})$-set of
$(\mathcal{B}_{2},C_{2})$. Note that

$\sum_{i=1}^{4}|R_{i}|=m_{1}^{\prime}+|\mathcal{A}_{3}^{\prime}|-m_{1}^{\prime}+n_{3}-1+n_{4}-1=n-1.$

Hence $R_{1}\cup R_{2}\cup R_{3}\cup R_{4}$ is a rainbow independent
$(n-1)$-set of $(\mathcal{F},G)$, a contradiction. By this claim, without loss
of generality, assume $h(\mathcal{A}_{3}^{\prime},V_{1})=n_{1}$ and so
$h(\mathcal{A}_{3}^{\prime},V_{2})=n_{2}-t+1$. Again by Lemma 3.1 (i) and
(ii), $\mathcal{A}_{3}^{\prime}$ can be partitioned into $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$ with $h(\mathcal{B}_{1},V_{1})=n_{1}$ and
$h(\mathcal{B}_{2},V_{2})=n_{2}-t+1$, furthermore, $|I\cap V_{1}|=n_{1}$ and
$|I\cap V_{2}|\leq n_{2}-t+1$ for any $I\in\mathcal{B}_{1}$. Hence $|I\cap
V_{4}|=n-\sum_{i=1}^{3}|I\cap V_{i}|\geq n-n_{1}-(n_{2}-t+1)-(n_{3}-1)=n_{4}$
for any $I\in\mathcal{B}_{1}$ and so
$\mathcal{B}_{1}\subset\mathcal{F}_{1}\cap\mathcal{F}_{4}$. Therefore, we have
$|\mathcal{F}_{4}|\geq n_{1}+n_{4}>2n_{4}-1$. By Proposition 1, we can find a
rainbow independent $n_{4}$-set $R_{4}^{\prime}$ of $(\mathcal{F}_{4},C_{4})$.
Let $\mathcal{F}^{\prime}=\mathcal{F}\setminus C_{R_{4}^{\prime}}$. Then
$|\mathcal{F}^{\prime}|=n-1-n_{4}$ and $|I\cap(V_{1}\cup V_{2}\cup
V_{3})|=n-n_{4}$ for every $I\in\mathcal{F}^{\prime}$. By the minimality of
$G$, there is a rainbow independent $(n-1-n_{4})$-set $R^{\prime}$ of
$(\mathcal{F}^{\prime},C_{1}\cup C_{2}\cup C_{3})$. Therefore,
$R_{4}^{\prime}\cup R^{\prime}$ is a rainbow independent $(n-1)$-set of
$(\mathcal{F},G)$, a contradiction too.

Now assume $m_{i}=n_{i}$ for all $i\in[3]$. By Corollary 2.4 (A), there is a
rainbow independent $(n_{3}-1)$-set $R_{3}$ of
$(\mathcal{F}_{3}\cap\mathcal{A},C_{3})$. Let
$\mathcal{B}=\mathcal{A}\setminus C_{R_{3}}$, we choose $C_{R_{3}}$ minimize
$\max\\{n_{1}-|\mathcal{B}\cap\mathcal{F}_{1}|,n_{2}-|\mathcal{B}\cap\mathcal{F}_{2}|\\}$.
By Claim 3, $m_{3}+h(\mathcal{A},V_{1}\cup V_{2})=|\mathcal{A}|+1$, i.e.,
$h(\mathcal{A},V_{1}\cup V_{2})=|\mathcal{B}|=n_{1}+n_{2}-t+1$. As discussed
in the above case, there is one of $h(\mathcal{B},V_{i}),\ i=1,2$ with
$h(\mathcal{B},V_{i})=n_{i}$. Without loss of generality, assume
$h(\mathcal{B},V_{1})=n_{1}$ and so $h(\mathcal{B},V_{2})=n_{2}-t+1$. Hence,
$n_{1}-|\mathcal{B}\cap\mathcal{F}_{1}|\leq 0$ and
$n_{2}-|\mathcal{B}\cap\mathcal{F}_{2}|\geq t-1\geq 2$. By Lemma 3.1 (i) and
(ii), $\mathcal{B}$ can be partitioned into $\mathcal{B}_{1}$ and
$\mathcal{B}_{2}$ with $h(\mathcal{B}_{1},V_{1})=n_{1}$ and
$h(\mathcal{B}_{2},V_{2})=n_{2}-t+1$, furthermore, for any
$I\in\mathcal{B}_{1}$, we have $|I\cap V_{1}|=n_{1}$ and $|I\cap V_{2}|\leq
n_{2}-t+1$. Hence, for any $I\in\mathcal{B}_{1}$, we have
$I\in\mathcal{F}_{3}$ or $I\in\mathcal{F}_{4}$ but $I\notin\mathcal{F}_{2}$.
If there is some $I\in\mathcal{F}_{3}$, reset $\mathcal{B}$ by replacing $I$
with some set in $\mathcal{F}_{2}\cap C_{R_{3}}$ (which is can be done since
$|\mathcal{F}_{2}\cap
C_{R_{3}}|=|\mathcal{A}\cap\mathcal{F}_{2}|-|\mathcal{B}\cap\mathcal{F}_{2}|\geq
n_{2}-|\mathcal{B}\cap\mathcal{F}_{2}|\geq 2$), the resulting new set
$\mathcal{B}$ has smaller
$\max\\{n_{1}-|\mathcal{B}\cap\mathcal{F}_{1}|,n_{2}-|\mathcal{B}\cap\mathcal{F}_{2}|\\}$,
a contradiction. So for any $I\in\mathcal{B}_{1}$, we have
$I\in\mathcal{F}_{4}$, i.e., $\mathcal{B}_{1}\subset\mathcal{F}_{4}$. Thus
$|\mathcal{F}_{4}|\geq n_{1}+n_{4}-1\geq 2n_{4}-1$. With the same discussion
with the end of the above case, we have a contradiction to the assumption that
$(\mathcal{F},G)$ has no rainbow independent $(n-1)$-set.

∎

##  4 Proof of Theorem 1.6

In this section, $C_{t}$ always denotes a cycle with vertex set $[t]$ and edge
set $\\{12,23,\ldots,(t-1)t,t1\\}$.

###### Proof of Theorem 1.6.

Let $\mathcal{F}\sqsubseteq\mathcal{I}_{n}(C_{t})$ with $|\mathcal{F}|=n$. We
show that there is a rainbow independent $n$-set of $(\mathcal{F},C_{t})$ if
$t>\frac{1}{3}n^{2}+\frac{44}{9}n$. Suppose to the contrary that
$(C_{t},\mathcal{F})$ has no rainbow independent $n$-set. Choose a member
$J\in\mathcal{F}$. By Corollary 2.4 (A), $(\mathcal{F}\setminus\\{J\\},C_{t})$
has a rainbow independent $(n-1)$-set $R$. Let $R^{\prime}=R\cap
N_{C_{t}}[J]$. Then $R^{\prime}$ is a rainbow independent set of
$(\mathcal{F}\setminus\\{J\\},C_{t})$ too. Choose such a $R$ with the smallest
$|R^{\prime}|$. We claim that $|R^{\prime}|\geq\lceil\frac{n}{2}\rceil$.
Otherwise, suppose $|R^{\prime}|<\frac{n}{2}$. Since $|N_{C_{t}}[i]\cap
N_{C_{t}}[j]|\leq 1$ for any two vertices $i,j\in J$ with $i\not=j$, every
vertex of $R^{\prime}$ is contained in at most two members of
$\\{N_{C_{t}}[i]:i\in J\\}$. So there exists a $j_{0}\in J$ with
$N_{C_{t}}[j_{0}]=[j_{0}-1,j_{0}+1]\cap R=\emptyset$. So we can enlarge $R$ by
adding $j_{0}$ with color $J$ to $R$, a contradiction to the assumption. Now
let $F=C_{t}-N_{C_{t}}[J\cup R]$. By the definition of $R$ and $R^{\prime}$,
$J\subseteq N_{C_{t}}[R^{\prime}]\subseteq N_{C_{t}}[R]$. So we have

$|N_{C_{t}}[J\cup R]|=|N_{C_{t}}[J]|+|N_{C_{t}}[R]|-|N_{C_{t}}[J]\cap
N_{C_{t}}[R]|\leq 3n+3n-|J|=5n.$

Recall that $C_{R^{\prime}}$ is the set of the corresponding colors assigned
to vertices in $R^{\prime}$. We claim that $C_{\mathcal{F}}(i)\cap
C_{R^{\prime}}=\emptyset$ for any $i\in V(F)$. If not, assume there is an
$I\in C_{\mathcal{F}}(i)\cap C_{R^{\prime}}$ for some $i\in V(F)$ and assume
$I$ is the color of $j$ in $R^{\prime}$, i.e. $C_{R^{\prime}}(j)=\\{I\\}$. Let
$\tilde{R}=(R\setminus\\{j\\})\cup\\{i\\}$. Then
$\tilde{R}^{\prime}=\tilde{R}\cap N_{C_{t}}[J]=R^{\prime}\setminus\\{j\\}$, a
contradiction to the minimality of $|R^{\prime}|$. This claim implies that for
any $I\in C_{R^{\prime}}\cup\\{J\\}$, we have $I\subseteq N_{C_{t}}[J\cup R]$.
Let $A=\\{(i,I):i\in I\mbox{ and }I\in\mathcal{F}\\}$, $B=\\{(i,I):i\in
V(F)\mbox{ and }i\in I,I\in\mathcal{F}\\}$ and $C=\\{(i,I):i\notin V(F)\mbox{
and }i\in I,I\in\mathcal{F}\\}$. So, with a double-counting argument, we have

${|B|=\sum_{i\in V(F)}c_{\mathcal{F}}(i)=|A|-|C|\leq
n^{2}-n|C_{R^{\prime}}\cup\\{J\\}|\leq\frac{1}{2}n^{2}-n\mbox{,}}$ (2)

where the inequality holds since
$|C_{R^{\prime}}|=|R^{\prime}|\geq\lceil\frac{n}{2}\rceil$. Note that
$N_{C_{t}}[J\cup R]$ is a union of intervals of length at least $3$ and
$|N_{C_{t}}[J\cup R]|\leq 5n$. So $N_{C_{t}}[J\cup R]$ consists of at most
$\frac{5n}{3}$ intervals. This implies that $F=C_{t}-N_{C_{t}}[J\cup R]$ has
at least $t-5n$ vertices and consists of $m\leq\frac{5n}{3}$ paths, say
$P_{1},P_{2},\ldots,P_{m}$. By Corollary 2.4 (B1), $c_{\mathcal{F}}(a)\geq 1$
for any $a\in[1,t]$. By Corollary 2.4 (B3), every path $P_{j}$ contains at
most $\frac{|V(P_{j})|+1}{2}$ vertices $a$ with $c_{\mathcal{F}}(a)=1$. Hence,

$\begin{split}\sum_{i\in F}c_{\mathcal{F}}(i)&=\sum_{j=1}^{m}\sum_{i\in
V(P_{j})}c_{\mathcal{F}}(i)\\\
&\geq\sum_{j=1}^{m}\left(2|V(P_{j})|-\frac{|V(P_{j})|+1}{2}\right)\\\
&=\frac{3}{2}\sum_{j=1}^{m}|V(P_{j})|-\frac{m}{2}\\\
&\geq\frac{3}{2}(t-5n)-\frac{m}{2}\\\
&\geq\frac{3}{2}t-\frac{25}{3}n\mbox{.}\end{split}$ (3)

From (2) and (3), we have

$\frac{3}{2}t-\frac{25}{3}n\leq\sum_{i\in
F}c_{\mathcal{F}}(i)\leq\frac{1}{2}n^{2}-n\mbox{,}$

i.e. $t\leq\frac{1}{3}n^{2}+\frac{44}{9}n$, a contradiction. ∎

##  5 Proof of Theorem 1.7

Let $\mathbb{Z}_{t}$ be the additive group of remainder of modulo $t$. For
$a,b\in\mathbb{Z}_{t}$, $a>b$ means $a\pmod{t}>b\pmod{t}$. For two sequences
$(a_{1},\ldots,a_{n}),(b_{1},\ldots,b_{n})\in\mathbb{Z}_{t}^{n}$,
$(a_{1},\ldots,a_{n})>(b_{1},\ldots,b_{n})$ if and only if there exists some
$i\in[n]$ such that $a_{i}>b_{i}$ and $a_{j}=b_{j}$ for all $j<i$.

Throughout this section, let $C_{t}$ be a cycle with vertex set
$\mathbb{Z}_{t}$ and edge set $\\{01,12,...,(t-1)0\\}$. If $t=2n+1$, by
Theorem 1.3, the result holds. So we assume $t\geq 2n+2$ in the following. Let
$\mathcal{F}=(B_{1},\ldots,B_{n})\sqsubseteq\mathcal{I}_{n}^{2}(C_{t})$.
Choose a maximal rainbow independent set $A=\\{a_{1},a_{2},\ldots,a_{r}\\}$ of
$(C_{t},\mathcal{F})$ with the property that $a_{1},\ldots,a_{r}$ are in a
clockwise order in $C_{t}$ and
$D_{A}=(a_{r}-a_{1},a_{2}-a_{1},a_{3}-a_{2},\ldots,a_{r}-a_{r-1})$ is minimal.
Without loss of generality, assume $C_{A}=\\{B_{1},B_{2},\ldots,B_{r}\\}$ and
$a_{1}=1$. Then we have $a_{1}<a_{2}<\ldots<a_{r}$ by the assumption of $A$.
It is sufficient to show that $r=n$. By Corollary 2.4 (A), we know $r\geq
n-1$. Suppose $r=n-1$. Define $A_{i}=\\{a_{i},a_{i}+1\\}$ for
$i=1,2,\ldots,n-1$. We have the following claims.

######  Claim 4.

$B_{n}\subseteq A\cup(A+1)\cup\\{a_{1}-1\\}$. Moreover, $0\in B_{n}$ and
$|B_{n}\cap A_{i}|=1$ for each $i\in[n-1]$.

###### Proof.

If there exists one $b\in B_{n}$ such that $b\notin A\cup(A+1)\cup(A-1)$, then
$\\{b\\}\cup A$ is a larger rainbow independent set than $A$, a contradiction.
Now suppose that there exists one $b\in B_{n}$ and an $i\in[2,r]$ with
$b=a_{i}-1$ but $b\neq a_{i-1}+1$. Then we can replace $a_{i}$ by $b$ in $A$
and get another rainbow independent set
$\\{a_{1},\ldots,a_{i-1},b,a_{i+1},\ldots,a_{r}\\}$ of $(\mathcal{F},C_{t})$
with $b-a_{i-1}<a_{i}-a_{i-1}$, a contradiction to the minimality of $D_{A}$.
So $B_{n}\subseteq A\cup(A+1)\cup\\{a_{1}-1\\}$.

Note that $A\cup(A+1)$ consists of exactly two independent sets of size $n-1$.
Since $|B_{n}|=n$, we have $a_{1}-1\in B_{n}$, i.e. $0\in B_{n}$ and
$|B_{n}\cap\\{a_{i},a_{i}+1\\}|=1$ for any $i\in[n-1]$. ∎

######  Claim 5.

If $C_{A}(a_{i})=B_{k_{i}}$ and $B_{n}\in C_{\mathcal{F}}(a_{i})$ for some
$i\geq 2$, then $B_{k_{i}}=B_{n}$.

###### Proof.

If $B_{k_{i}}\not=B_{n}$, then we can reset the color of $a_{i}$ by $B_{n}$
and apply Claim 4 to $B_{k_{i}}$, we have $0\in B_{k_{i}}$ and $|B_{k_{i}}\cap
A_{\ell}|=1$ for every $\ell\in[n-1]$. Since $B_{k_{i}}\neq B_{n}$, we have
$s(B_{k_{i}})\not=s(B_{n})$. Without loss of generality, we assume $0\leq
s(B_{k_{i}})<s(B_{n})$. Let $B_{n}=(j,j+2,\ldots,0,2,\ldots,2n-t+j-2)$. Then
$j>0$ and $2n-t+j-2<j$ (otherwise, we have $t\leq 2n-2$, a contradiction). So,
by Claim 4, $t-2$ must be in $A_{n-1}$ and $j$ must be in $A_{s}$, where
$s=n-\frac{t-j}{2}$. If $s(B_{k_{i}})=0$ then $B_{k_{i}}=(0,2,\ldots,2n-2)$.
So we have $2n-2\in A_{n-1}$, i.e. $a_{n-1}=2n-3$ or $2n-2$. In any case, we
have $t\leq 2n+1$, a contradiction. Now assume $s(B_{k_{i}})=h\not=0$. Then
$B_{k_{i}}=\\{h,h+2,\ldots,0,2,\ldots,2n-t+h-2\\}$. Hence $h$ and $j$ have the
same parity. So $j-2\in B_{k_{i}}$ but $j-2\notin B_{n}$ because
$j-(2n-t+j-2)=t-2n+2\geq 4$. Since $j\in B_{n}\cap A_{s}$, we have $2n-t+j-2$
must be in $B_{n}\cap A_{s-1}$. Since $A_{s}\cap A_{s-1}=\emptyset$ and
$2n-t+j-2<j-2<j$, there is no $A_{\ell}$ containing $j-2$ for $\ell\in[n-1]$.
This is a contradiction to $|B_{k_{i}}\cap A_{\ell}|=1$ for all
$\ell\in[n-1]$. ∎

If $s(B_{n})=0$, i.e., $B_{n}=\\{0,2,\ldots,2n-2\\}$. Since $A$ is an
independent set with $a_{1}=1\in A$ and $|B_{n}\cap\\{a_{i},a_{i}+1\\}|=1$ for
every $i\in[n-1]$, there exists an integer $k$ with $1<k\leq n$ such that
$a_{i}=2i-1$ for $1\leq i<k$ and $a_{i}=2i$ for $i\geq k$ (if $k<n$). By Claim
5, we have $B_{i}=B_{n}$ for all $i\geq k$. Clearly, $2n\notin B_{i}$ for all
$i\in[k,n]$. If $t=2n+2$, since $a_{i}=2i-1\in B_{i}$ and $B_{i}$ is 2-jump,
we have $2n\notin B_{i}$ for all $i\in[k-1]$. Therefore, $2n\notin B_{i}$ for
all $i\in[n]$, which is a contradiction to Corollary 2.4 (B1). If $t>2n+2$,
then $t-3>2n-1>a_{n-1}$. Clearly, $t-3\notin B_{n}$. Let $\ell\leq k-1$ be the
minimal number with $t-3\in B_{\ell}$ (If such $\ell$ does not exist, then
$t-3\notin B_{i}$ for all $i\in[n]$, a contradiction to Corollary 2.4 (B1),
too). Since $B_{i}\in\mathcal{I}_{n}^{2}(C_{t})$ with $a_{i}=2i-1\in B_{i}$
and $t-3\notin B_{i}$ for any $i<\ell$, we have $a_{i}+2=a_{i+1}\in B_{i}$. So
we can recolor $a_{i+1}$ with $B_{i}$ for all $i\in[\ell-1]$, remain the color
of $a_{i}$ unchanged for $i\in[\ell+1,n-1]$ and color $t-3$ with $B_{\ell}$
and 0 with $B_{n}$, i.e. $(A\setminus\\{1\\})\cup\\{0,t-3\\}$ is a rainbow
independent $n$-set of $(\mathcal{F},C_{t})$, a contradiction.

Now suppose $s(B_{n})=-2(n-m)$ for some $n>m>0$, i.e.,
$B_{n}=\\{t-2(n-m),\ldots,t-2,0,2,\ldots,2m-2\\}$. If $t=2n+2$, then
$B_{n}=\\{2m+2,\ldots,2n,0,2,\ldots,2m-2\\}$. Clearly, $2m-1\notin A$
(otherwise, $B_{n}\cap\\{2m-1,2m\\}=\emptyset$, a contradiction to Claim 4).
With the same reason as the case $s(B_{n})=0$, we have an integer $k$ with
$1<k\leq m$ such that $a_{i}=2i-1$ for any $i\in[k-1]$ and $a_{i}=2i$ for any
$i\in[k,m-1]$. With the same discussion with the case $s(B_{n})=0$, we have
$2m\notin B_{i}$ for all $i\in[m-1]$. For $i=m$, we have $a_{m}\not=2m$
(otherwise, $B_{n}\cap\\{a_{m},a_{m}+1\\}=\emptyset$, a contradiction to Claim
4). So $a_{i}>2m$ for any $i\in[m,n-1]$. Since $B_{j}$ is 2-jump, all elements
of $B_{j}$ have the same parity. By Claim 5, $B_{j}=B_{n}$ if $a_{j}\in B_{j}$
is an even numbers when $j\in[m,n-1]$. So $2m\notin B_{j}$ for any
$j\in[m,n-1]$. Therefore, we have $2m\notin B_{i}$ for all $i\in[n]$, a
contradiction to Corollary 2.4 (B1). If $t>2n+2$, then by Claim 4, we have
$a_{i}\in\\{t-2n+2i,t-2n+2i-1\\}$ for $i\in[m,n-1]$, and
$a_{i}\in\\{2i-1,2i\\}$ for $i\in[2,m-1]$. In particular we have
$a_{n-1}\in\\{-2,-3\\}$. If $a_{n-1}=-2$, then $a_{1}-a_{n-1}=3$ and
$a_{m}-a_{m-1}\geq t-2n+2m-1-2(m-1)>3$, we have a contradiction to the
minimality of $D_{A}$ by reordering $A$ with
$A=\\{a_{m},a_{m+1}...,a_{n-1},a_{1},...a_{m-1}\\}$. So we have $a_{n-1}=-3$,
which implies that $a_{i}=t-2n+2i-1$ for every $i\in[m,n-1]$. In particular,
$a_{m}=t-2(n-m)-1\in B_{m}$. Note that $a_{m}-2=t-2(n-m)-3>2m-1>a_{m-1}$. By
the minimality of $D_{A}$, we have $-2(n-m)-3\notin B_{m}$ (otherwise, we can
reduce $a_{m}-a_{m-1}$ by replacing $a_{m}$ with $a_{m}-2$ in $A$). Since
$B_{m}$ is 2-jump, we have $s(B_{m})=t-2(n-m)-1$ and so $-1\in B_{m}$. Then
$A^{\prime}=(A\setminus\\{a_{m}\\})\cup\\{-1\\}=\\{a_{m+1},\ldots,a_{n-1},-1,a_{1},\ldots,a_{m-1}\\}$
is a rainbow independent set of $(\mathcal{F},C_{t})$ with
$a_{m+1}-a_{m-1}\geq t-2n+2m+1-2(m-1)>5>4=a_{1}-a_{n-1}$, a contradiction to
the minimality of $D_{A}$.

This completes the proof of Theorem 1.7.

##  6 Concluding remarks and discussions

In this article, we show that (1) Conjecture 1.1 is true when
$|V(G)|\in\\{2n-1,2n\\}$ and (2) if Conjecture 1.2 is ture then Conjecture 1.1
holds for graphs $G\in\mathcal{D}(2)$ with $c_{e}(G)\leq 3$. We believe that
Conjecture 1.2 implies Conjecture 1.1, we leave this as an open problem. For
Conjecture 1.2, it has been shown that this conjecture is true for the base
case (Theorem 1.3) and for large $t$ (Theorem 1.6). Could we show the rest
case of Conjecture 1.2?

## References

  * [1] R. Aharoni, E. Berger, Rainbow matchings in $r$-partite $r$-graphs, Electron. J. Combin. 16 (2009), $\sharp$R119.
  * [2] R. Aharoni, E. Berger, M. Chudnovsky, D. Howard, P. Seymour, Large rainbow matchings in general graphs, European J. Combin., 79 (2019), pp. 222–227.
  * [3] R. Aharoni, J. Briggs, J. Kim, M. Kim, Rainbow independent sets in certain classes of graphs, arXiv: 1909.13143.
  * [4] R. Aharoni, J. Briggs, J. Kim, M. Kim, Badges and rainbow matchings, Discrete Math., 344 (6) (2021), Article 112363.
  * [5] R. Aharoni, R. Holzman, Z. Jiang, Rainbow fractional matchings, Combinatorica 39 (2019), 1191–1202. https://doi.org/10.1007/s00493-019-4019-y.
  * [6] R. Aharoni, D. Kotlar, R. Ziv, Uniqueness of the extreme cases in theorems of Drisko and Erdős-Ginzburg-Ziv, Eur. J. Combin. 67 (2018), 222–229.
  * [7] J. Barát, A. Gyárfás, G. Sárközy, Rainbow matchings in bipartite multigraphs, Period. Math. Hung. 74 (2017) 108–111.
  * [8] A. A. Drisko, Transversals in row-latin rectangles, J. Combin. Theory, Ser. A 84 (1998), 181–195.
  * [9] J. Kim, M. Kim, O. Kwon, Rainbow independent sets on dense graph classes, Discrete Applied Mathematics (2021), https://doi.org/10.1016/j.dam.2021.04.007.
  * [10] Z. Lv, M. Lu, Rainbow independent sets in cycles, arXiv: 2103.05202.