Rainbow cycles through specified vertices Henry Liu School of Mathematics Sun
Yat-sen University Guangzhou 510275, China<EMAIL_ADDRESS>4 May
2024

###### Abstract

An edge-coloured cycle is _rainbow_ if the edges have distinct colours. Let
$G$ be a graph such that any $k$ vertices lie in a cycle of $G$. The _$k$
-rainbow cycle index_ of $G$, denoted by $crx_{k}(G)$, is the minimum number
of colours required to colour the edges of $G$ such that, for every set $S$ of
$k$ vertices in $G$, there exists a rainbow cycle in $G$ containing $S$. In
this paper, we will first prove some results about the parameter $crx_{k}(G)$
for general graphs $G$. One of the results is a classification of all graphs
$G$ such that $crx_{k}(G)=e(G)$, for $k=1,2$. We will also determine
$crx_{k}(G)$ for some specific graphs $G$, including wheels, complete graphs,
complete bipartite and multipartite graphs, and discrete cubes.

AMS Subject Classification (2020): 05C15, 05C38

Keywords: Edge-colouring; rainbow coloured cycle; specified vertices

##  1 Introduction

In this paper, all graphs are simple and finite. Let $K_{t}$ and $C_{t}$
denote the complete graph and the cycle on $t$ vertices. Let $G$ be a graph
with vertex set $V(G)$ and edge set $E(G)$. For disjoint sets $X,Y\subset
V(G)$, let $E(X,Y)$ denote the edges of $G$ with one end-vertex in $X$ and the
other in $Y$. Let $[X,Y]$ be the bipartite subgraph of $G$ with classes $X$
and $Y$, and edge set $E(X,Y)$. For $r\in\mathbb{N}$, an _$r$ -colouring_ of
$G$ is a function $\phi:E(G)\to\\{1,2,\dots,r\\}$, and $\phi$ is _proper_ if
$\phi(e)\neq\phi(e^{\prime})$ whenever $e$ and $e^{\prime}$ are adjacent
edges. We will often refer the values $1,2,\dots,r$ as _colours_ , and we may
also call $\phi$ an _edge-colouring_ or _colouring_. For $k\in\mathbb{N}$, a
graph $G$ is _$k$ -connected_ if $|V(G)|>k$, and for every $C\subset V(G)$
with $|C|\leq k-1$, the subgraph $G-C$ is connected. For any other undefined
terms in graph theory, the reader is referred to book of Bollobás [7].

The topic of colourings of graphs has a long history which dates back to the
famous _Four-colour conjecture_ from the 1850s. For edge-colourings, a
landmark result is due to Vizing [33] in 1964 which states that
$\chi^{\prime}(G)\in\\{\Delta(G),\Delta(G)+1\\}$ for any graph $G$, where
$\chi^{\prime}(G)$ and $\Delta(G)$ are the _edge-chromatic number_ (or
_chromatic index_) and _maximum degree_ of $G$. A significant direction in the
topic, introduced independently in the late 1970s by Vizing [34]; and by
Erdős, Rubin and Taylor [18], is _list colourings_. A famous open problem is
the _List colouring conjecture_ , which states that
$\chi^{\prime}(G)=\chi^{\prime}_{\ell}(G)$ for any graph $G$, where
$\chi^{\prime}_{\ell}(G)$ is the _list edge-chromatic number_ of $G$. This
conjecture first appeared in print in a paper of Bollobás and Harris [9] in
1985. There is a vast amount of literature about colourings of graphs, and a
good starting reference is the book by Jensen and Toft [23].

Problems in graph theory concerning cycles through specified vertices have
been well-studied. A well-known result of Dirac [16] from 1960, which can be
proved by using Menger’s theorem [29], states that for $k\geq 2$, any $k$
specified vertices in a $k$-connected graph lie in a cycle. Since then, many
problems and results in this topic have appeared. Bondy and Lovász [11] proved
that for $k\geq 2$, any $k-1$ specified vertices in a $k$-connected non-
bipartite graph lie in an _odd_ cycle; and for $k\geq 3$, any $k$ specified
vertices in a $k$-connected graph lie in an _even_ cycle. When considering the
degrees of a graph, another famous result of Dirac [15] from 1952 states that,
any graph of order $n\geq 3$ with minimum degree at least $\frac{n}{2}$
contains a Hamilton cycle. This theorem has been generalised in many
directions. One generalisation is by Bollobás and Brightwell [8]. They proved
that, if $n\geq k\geq 3$ and $d\geq 1$ are such that
$s=\big{\lceil}\frac{k}{\lceil n/d\rceil-1}\big{\rceil}\geq 3$, then for any
$k$ vertices of degree at least $d$ in a graph of order $n$, there exists a
cycle containing at least $s$ of the vertices.

An edge-coloured graph is _rainbow_ if all the edges have distinct colours.
Another popular research topic considers the presence of rainbow coloured
subgraphs in edge-coloured graphs. One direction is _anti-Ramsey numbers_ ,
which was initiated by Erdős, Simonovits and Sós [19] in 1973. See [4, 24, 31]
for results that involve rainbow cycles. A more recent direction is _rainbow
Turán numbers_ , which was proposed by Keevash et al. [26] in 2007. Many
problems about rainbow cycles in edge-coloured graphs have also been
considered. See for example, [1, 3, 5, 17, 21, 22].

In this paper, we consider the following problem. _For $k\geq 1$, let
$\mathcal{F}_{k}$ denote the family of all graphs $G$ with the property that
any $k$ vertices of $G$ lie in a cycle. Consider an edge-colouring of
$G\in\mathcal{F}_{k}$ such that, any $k$ vertices lie in a rainbow cycle. What
is the minimum number of colours in such an edge-colouring?_ Any edge-
colouring satisfying the condition of the problem is called a _$k$ -rainbow
cycle colouring_, and a $1$-rainbow cycle colouring is simply called a
_rainbow cycle colouring_. For $G\in\mathcal{F}_{k}$, the minimum number of
colours in a $k$-rainbow cycle colouring of $G$ is denoted by $crx_{k}(G)$,
and is called the _$k$ -rainbow cycle index_ of $G$. Thus, $crx_{k}(G)$ is
well-defined if and only if $G\in\mathcal{F}_{k}$. The parameter $crx_{k}(G)$
can be considered as a type of edge-chromatic number. Moreover, the problem of
the study of $crx_{k}(G)$ can be classed under both of the “cycles through
specified vertices” and “rainbow cycles in graphs” themes.

There are conceivably some real-world applications. For example, suppose that
a certain country is served by many different airlines, where some pairs of
cities are connected directly by exactly one airline. A travelling salesman
wants to attend business meetings in $k$ designated cities in no particular
order, visiting each city once, and returning to his originating city. Between
two consecutive designated cities, he can travel via other cities, and in the
entire trip, he never visits any city more than once. What is the minimum
number of airlines that the country needs so that, for any choice of $k$
designated cities, the travelling salesman can always complete his trip, using
a different airline between any two consecutive cities that he visits? This
minimum is precisely $crx_{k}(G)$, where $G$ is the graph whose vertex set
consists of all the cities, and two vertices of $G$ are adjacent if and only
if the corresponding two cities are connected directly by an airline.

We note that Chartrand, Okamoto and Zhang [13] considered the _$k$ -rainbow
index_, which is the analogous parameter with “tree” in place of “cycle”. For
a connected graph $G$ on $n$ vertices and $2\leq k\leq n$, the _$k$ -rainbow
index_, denoted by $rx_{k}(G)$, is the minimum number of colours needed to
colour the edges of $G$ so that, any $k$ vertices of $G$ are connected by a
rainbow tree. Trivially, we also let $rx_{1}(G)=0$ for every graph $G$ (not
necessarily connected). We remark that the $k$-rainbow cycle index
$crx_{k}(G)$ has previously been studied by Li et al. [28], when they proved
some computational complexity results. The problem of the study of the
parameter $crx_{k}(G)$ was in fact originally introduced by the present author
to the authors of [28].

The family $\mathcal{F}_{k}$ contains some important subfamilies of graphs,
including all Hamiltonian and pancyclic graphs on at least $k$ vertices. Also,
for $k\geq 2$, Dirac’s theorem [16] implies that $\mathcal{F}_{k}$ contains
all $k$-connected graphs. Conversely, if $G\in\mathcal{F}_{k}$ ($k\geq 2$),
then it is necessary that $G$ is $2$-connected. In Proposition 3, we
characterise the families $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$, where
$\mathcal{F}_{2}$ is precisely the family of all $2$-connected graphs. For
$k\geq 3$, no simple characterisation of the graphs of $\mathcal{F}_{k}$ is
known, and only some sufficient conditions for graphs to be in
$\mathcal{F}_{k}$ have been found [11, 15].

Some initial observations can be made. Clearly, we have
$\mathcal{F}_{1}\supset\mathcal{F}_{2}\supset\mathcal{F}_{3}\supset\cdots$. If
$G\in\mathcal{F}_{k}$, and $g(G)$ and $c(G)$ denote the _girth_ and
_circumference_ of $G$, then we have $3\leq g(G)\leq crx_{1}(G)\leq
crx_{2}(G)\leq\cdots\leq crx_{k}(G)\leq e(G)$ and
$k\leq\min(crx_{k}(G),c(G))$. Also, we have $crx_{k}(G)>rx_{k}(G)$. We will
see in Theorem 7 that for any $k\geq 1$, the difference $crx_{k}(G)-rx_{k}(G)$
can be small (at most $3$) for infinitely many graphs $G$, and can also be
arbitrarily large. If $G,H\in\mathcal{F}_{k}$, and $H$ is a spanning subgraph
of $G$, then $crx_{k}(G)\leq crx_{k}(H)$.

This paper is organised as follows. In Section 2, we shall study the parameter
$crx_{k}(G)$ for general graphs $G$. In particular, we shall characterise the
graphs $G\in\mathcal{F}_{k}$ such that $crx_{k}(G)=e(G)$ for $k=1,2$. In
Section 3, we will compute exactly or find tight estimates for $crx_{k}(G)$
for some specific graphs $G$, including wheels, complete graphs, complete
bipartite and multipartite graphs, and discrete binary cubes.

##  2 General graphs

In this section, we shall prove some results about the parameter $crx_{k}(G)$
for general graphs $G$. We begin by recalling some well-known concepts about
$2$-connected graphs.

A _block_ of a graph is a subgraph which is either an isolated vertex, or a
bridge (i.e., a cut-edge), or a maximal $2$-connected subgraph (i.e., not
strictly contained in another $2$-connected subgraph). Any graph $G$ has a
unique _block decomposition_ into blocks $B_{1},\dots,B_{p}$ for some $p\geq
1$, such that the edge sets $E(B_{1}),\dots,E(B_{p})$ form a disjoint union of
$E(G)$, and any two blocks are either vertex-disjoint, or meet at a cut-vertex
of $G$. An _end-block_ is a block which is incident with at most one cut-
vertex. If $G$ is connected and is not a block, then $G$ has at least two end-
blocks, each of which contains exactly one cut-vertex. For further details,
see [6] (Ch. I) and [7] (Ch. III.2).

A graph $G$ is _minimally $k$-connected_ if $G$ is $k$-connected, and for
every edge $e\in E(G)$, the graph $G-e$ is not $k$-connected. The following
result describes the structure of minimally $2$-connected graphs.

######  Theorem 1 ([6], Ch. I, Theorem 3.1).

Let $G$ be a minimally $2$-connected graph, and $xy\in E(G)$. Then, $G-xy$ has
no isolated vertex and at least two blocks. The blocks of $G-xy$, say
$B_{1},\dots,B_{p}$ for some $p\geq 2$, can be ordered linearly so that
$V(B_{i})\cap V(B_{i+1})=\\{v_{i}\\}$ for $1\leq i<p$, where
$v_{1},\dots,v_{p-1}$ are all the cut-vertices of $G-xy$. The end-blocks of
$G-xy$ are $B_{1}$ and $B_{p}$. Moreover, we have $x\in
V(B_{1})\setminus\\{v_{1}\\}$ and $y\in V(B_{p})\setminus\\{v_{p-1}\\}$. See
Figure 1.

Figure 1. The structure of $G$ in Theorem 1

Finally, we have the following well-known result about the structure of
$2$-connected graphs. See for example [14], Ch. 3, Proposition 3.1.1.

######  Theorem 2.

A graph is $2$-connected if and only if it can be obtained from a cycle,
followed by successively attaching a non-trivial path by identifying the end-
vertices with two distinct vertices of the previous graph.

In Theorem 2, each attached path is called an _ear_ , and the initial cycle,
together with the ears, form an _ear decomposition_ for the $2$-connected
graph.

Now, we present the results. Recall that $crx_{k}(G)$ is well-defined if and
only if $G\in\mathcal{F}_{k}$. We first give characterisations of the families
$\mathcal{F}_{1}$ and $\mathcal{F}_{2}$. For $k\geq 3$, we have already
mentioned that characterising the graphs of $\mathcal{F}_{k}$ is a much more
difficult problem.

######  Proposition 3.

  1. (a)

$\mathcal{F}_{1}$ is the family of all graphs with the property that, every
vertex belongs to a $2$-connected block in the block decomposition.

  2. (b)

$\mathcal{F}_{2}$ is the family of all $2$-connected graphs.

###### Proof.

(a) Let $G$ be a graph with the property as stated, so that any vertex $v\in
V(G)$ belongs to a $2$-connected subgraph. By Dirac’s theorem [16], $v$ lies
in a cycle. Hence, $G\in\mathcal{F}_{1}$.

Conversely, suppose that $G$ does not have the stated property. If $G$ has an
isolated vertex $u$, then $u$ does not lie in a cycle, and
$G\not\in\mathcal{F}_{1}$. Otherwise, $G$ has a vertex $v$ such that, in the
block decomposition of $G$, every block containing $v$ is a bridge of $G$. If
$v$ lies in a cycle $C$ of $G$, then the two edges of $C$ incident with $v$
are bridges of $G$. This is a contradiction, since no bridge of $G$ can lie in
a cycle of $G$. Hence, $v$ does not lie in a cycle of $G$, and
$G\not\in\mathcal{F}_{1}$.
(b) By Menger’s theorem [29], $G$ is $2$-connected if and only if any two
vertices of $G$ have two internally vertex-disjoint paths connecting them.
Equivalently, any two vertices of $G$ have a cycle containing them, which is
equivalent to $G\in\mathcal{F}_{2}$. ∎

Next, recall that $crx_{k}(G)\leq e(G)$ for $G\in\mathcal{F}_{k}$. We may ask:
_For what graphs $G$ do we have $crx_{k}(G)=e(G)$?_ The analogous result for
$rx_{k}(G)$ can be seen from Chartrand et al. [13]: _For a connected graph $G$
on $n$ vertices and $2\leq k\leq n$, we have $rx_{k}(G)=e(G)$ if and only if
$G$ is a tree._ Here, we have the following result.

######  Theorem 4.

Let $G$ be a graph of order $n\geq 3$.

  1. (a)

Let $G\in\mathcal{F}_{1}$. Then $crx_{1}(G)=e(G)$ if and only if $G$ is the
cycle $C_{n}$.

  2. (b)

Let $G\in\mathcal{F}_{2}$. Then $crx_{2}(G)=e(G)$ if and only if $G$ is
minimally $2$-connected.

  3. (c)

Let $G\in\mathcal{F}_{n}$ (equivalently, $G$ is Hamiltonian), and $1\leq k\leq
n$. Then $crx_{k}(G)=e(G)$ if and only if $G$ is the cycle $C_{n}$.

###### Proof.

(a) If $G=C_{n}$, then clearly we have $crx_{1}(G)=e(G)$.

Conversely, suppose that $G\neq C_{n}$. If $G$ is $2$-connected, then by
Theorem 2, $G$ has an ear decomposition with at least one ear. Let $P$ be the
final ear attached, and $G^{\prime}$ be the subgraph of $G$ before $P$ is
attached. Let $u,v\in V(G^{\prime})$ be the end-vertices of $P$, and $e\in
E(P)$. Let $P^{\prime}\subset G^{\prime}$ be a $u-v$ path. Now, assign a
rainbow colouring to $G-e$, and then assign a used colour not in $P\cup
P^{\prime}$ to $e$. We have a rainbow cycle colouring of $G$ with fewer than
$e(G)$ colours, since every vertex of $G^{\prime}$ lies in a rainbow cycle in
$G^{\prime}$ (since $G^{\prime}$ is $2$-connected), and every vertex of $P$
lies in the rainbow cycle $P\cup P^{\prime}$.

Otherwise, $G$ is not $2$-connected, so that the block decomposition of $G$
consists of at least two blocks. By Proposition 3(a), no block is an isolated
vertex of $G$, and every vertex of $G$ belongs to a $2$-connected block. We
colour the edges of $G$ in such a way that every block is rainbow coloured,
and two of the blocks have a colour in common. This is a rainbow cycle
colouring with fewer than $e(G)$ colours, since any vertex lies in a rainbow
cycle in a $2$-connected block which contains the vertex.
(b) Suppose that $G$ is not minimally $2$-connected. Then there exists $e\in
E(G)$ such that $G-e$ is $2$-connected. We assign a rainbow colouring to
$G-e$, and then assign a used colour to $e$. This is a $2$-rainbow cycle
colouring using fewer than $e(G)$ colours.

Conversely, suppose that $G$ is minimally $2$-connected, and we have a
colouring of $G$ with fewer than $e(G)$ colours. Then there exist
$e,e^{\prime}\in E(G)$ with the same colour. By Theorem 1, the block
decomposition of $G-e$ has the following structure. The blocks are
$B_{1},\dots,B_{p}$ for some $p\geq 2$, and can be ordered linearly so that
$V(B_{i})\cap V(B_{i+1})=\\{x_{i}\\}$ for $1\leq i<p$, where
$x_{1},\dots,x_{p-1}$ are all the cut-vertices of $G-e$, and the end-blocks
are $B_{1}$ and $B_{p}$. Moreover, we have $e=x_{0}x_{p}$, where $x_{0}\in
V(B_{1})\setminus\\{x_{1}\\}$ and $x_{p}\in V(B_{p})\setminus\\{x_{p-1}\\}$.
Let $e^{\prime}\in E(B_{\ell})$. We may assume that $1<\ell\leq p$. If
$B_{\ell}$ is a bridge of $G-e$, then $e^{\prime}=x_{\ell-1}x_{\ell}$, and any
cycle of $G$ containing $x_{0}$ and $x_{\ell}$ must use both $e$ and
$e^{\prime}$. Otherwise, we have $B_{\ell}$ is minimally $2$-connected, since
$G$ is minimally $2$-connected. Again by Theorem 1, the blocks of
$B_{\ell}-e^{\prime}$ can be linearly ordered as $D_{1},\dots,D_{q}$ for some
$q\geq 2$, where $V(D_{j})\cap V(D_{j+1})=\\{y_{j}\\}$ for $1\leq j<q$, and
$y_{1},\dots,y_{q-1}$ are all the cut-vertices of $B_{\ell}-e^{\prime}$.
Moreover, we have $e^{\prime}=y_{0}y_{q}$, where $y_{0}\in
V(D_{1})\setminus\\{y_{1}\\}$ and $y_{q}\in V(D_{q})\setminus\\{y_{q-1}\\}$.
Now, we have $x_{\ell-1},x_{\ell}\in V(B_{\ell})$. We may assume that
$x_{\ell-1}\in V(D_{s})$ and $x_{\ell}\in V(D_{t})$ for some $1\leq s\leq
t\leq q$. Note that $s$ and $t$ may possibly be not unique. If we must have
$s=1$ and $t=q$, then $G-e^{\prime}$ would be $2$-connected, a contradiction.
If $1\leq s\leq t<q$, for a cycle $C$ to contain $x_{0}$ and $y_{q}$,
emanating from $x_{0}$, we must use the edge $e$ and a path in $B_{1}$
connecting $x_{0}$ and $x_{1}$; and emanating from $y_{q}$, we must use the
edge $e^{\prime}$ and a path in $D_{q}$ connecting $y_{q}$ and $y_{q-1}$.
Hence $C$ must use both $e$ and $e^{\prime}$. If $1<s\leq t\leq q$, for a
cycle $C$ to contain $x_{0}$ and $y_{0}$, again $C$ must use $e$; and
emanating from $y_{0}$, we must use the edge $e^{\prime}$ and a path in
$D_{1}$ connecting $y_{0}$ and $y_{1}$. Again, $C$ must use both $e$ and
$e^{\prime}$.

We conclude that there are always two vertices of $G$ such that, any cycle in
$G$ containing them must use both $e$ and $e^{\prime}$. Hence, there is no
$2$-rainbow cycle colouring with fewer than $e(G)$ colours, and
$crx_{2}(G)=e(G)$.
(c) If $G=C_{n}$, then clearly we have $crx_{k}(G)=e(G)$. Conversely, suppose
that $G\neq C_{n}$. Since $G$ is Hamiltonian, we have $e(G)>n$. By taking an
$n$-colouring of $G$ such that a Hamilton cycle is rainbow, we have
$crx_{k}(G)\leq n$. Therefore, $crx_{k}(G)<e(G)$. ∎

For $3\leq k<n$, the problem of classifying all graphs $G\in\mathcal{F}_{k}$
of order $n$ with $crx_{k}(G)=e(G)$ seems to be more difficult. The case when
$k=n-1$ seems interesting. In this case, if $G$ is Hamiltonian, then we must
have $G=C_{n}$. Otherwise, $G$ must be hypohamiltonian, i.e., $G$ is not
Hamiltonian, and $G-v$ is Hamiltonian for every $v\in V(G)$. Classifying
hypohamiltonian graphs with a fixed order is a problem of significant
interest. The hypohamiltonian graph with the smallest order is the Petersen
graph ${\sf P}_{10}$, with $10$ vertices. Aldred, McKay and Wormald [2] found
all hypohamiltonian graphs of order at most $17$. There is one such graph when
the order is $10$ (the Petersen graph), $13$ or $15$, there are four graphs of
order $16$, and none with orders $11,12,14,17$. These graphs are shown in
Figure 2.

Figure 2. Hypohamiltonian graphs with at most $17$ vertices

For the four graphs of order $16$, an edge connecting the centre vertex $a$ to
the outside cycle is a _spoke edge_. In the next result, we show that, with
the exception of the Petersen graph, we have $crx_{n-1}(G)<e(G)$ if $G$ is one
of the graphs in Figure 2 and has order $n$.

######  Theorem 5.

  1. (a)

If ${\sf P}_{10}$ is the Petersen graph, then $crx_{9}({\sf P}_{10})=e({\sf
P}_{10})=15$.

  2. (b)

If $G$ is a hypohamiltonian graph of order $n$, where $11\leq n\leq 17$, then
$crx_{n-1}(G)<e(G)$.

###### Proof.

(a) Suppose that we have a colouring of ${\sf P}_{10}$, using fewer than
$e({\sf P}_{10})=15$ colours. Then, two edges $e,e^{\prime}$ have the same
colour. We choose a vertex $v$ as follows. If $e$ and $e^{\prime}$ are
adjacent, say at $u$, then we let $v$ be the vertex adjacent to $u$ and not in
$e$ or $e^{\prime}$. If $e$ and $e^{\prime}$ are not adjacent, then we choose
$v$, not in $e$ or $e^{\prime}$, which is adjacent to an end-vertex of $e$ and
$e^{\prime}$. Now, since ${\sf P}_{10}$ is hypohamiltonian, any cycle of ${\sf
P}_{10}$ containing all vertices of ${\sf P}_{10}-v$ must use $e$ and
$e^{\prime}$, and hence is not rainbow. Therefore, $crx_{9}({\sf
P}_{10})=e({\sf P}_{10})=15$.
(b) We show that if $G$ is one of the remaining graphs in Figure 2, with order
$n$, then $crx_{n-1}(G)<e(G)$. Since $H_{16}$ is a spanning subgraph of both
$H_{16}^{1}$ and $H_{16}^{2}$, the results for $H_{16}^{1}$ and $H_{16}^{2}$
follow from that of $H_{16}$. For the remaining four graphs, consider the
colouring of $G$ where the edges $e,e^{\prime}$ as shown in Figure 2 have the
same colour, and the remaining edges have further distinct colours. We claim
that this is an $(n-1)$-rainbow cycle colouring for $G$. It suffices to show
that $G-v$ contains a Hamilton cycle not using $e$ or $e^{\prime}$ for every
$v\in V(G)$, which therefore is a rainbow cycle. Clearly, it suffices to check
this property when $v$ is not an end-vertex of $e$ or $e^{\prime}$.

First, consider $G=H_{13}$. Note that $H_{13}$ contains a subdivided Petersen
graph as a spanning subgraph, and not using $e^{\prime}$. Then, $H_{13}-v$
contains a Hamilton cycle not using $e^{\prime}$ for $v\in
V(H_{13})\setminus\\{x,x^{\prime},y,y^{\prime},z\\}$. Figure 3(a) shows that
both $H_{13}-x$ and $H_{13}-y$ (and thus also $H_{13}-x^{\prime}$ and
$H_{13}-y^{\prime}$ by symmetry) contains a Hamilton cycle, not using $e$ or
$e^{\prime}$.

Next, consider $G=H_{15}$. Figure 3(b) shows that each of
$H_{15}-w,H_{15}-x,H_{15}-y$ and $H_{15}-z$ contains a Hamilton cycle, using
either $e,f^{\prime}$ or $e^{\prime},f$. Hence by symmetry, $H_{15}-v$
contains a Hamilton cycle not using $e$ or $e^{\prime}$, for every $v\in
V(H_{15})\setminus\\{a\\}$.

Next, consider $G=H_{16}$. Figure 3(c) shows that both $H_{16}-x$ and
$H_{16}-y$ contains a Hamilton cycle that uses exactly two consecutive spoke
edges. By symmetry, the same is true for $H_{16}-v$, for every $v\in
V(H_{16})\setminus\\{a\\}$. Any such cycle does not use $e$ or $e^{\prime}$.

Finally, consider $G=H_{16}^{\prime}$. Figure 3(d) shows that
$H_{16}^{\prime}-x_{i}$ contains a Hamilton cycle not using $e$ or
$e^{\prime}$, for $0\leq i\leq 3$. We have the automorphisms $\tau$ and
$\sigma$ on $H_{16}^{\prime}$, where $\tau$ is the obvious symmetry; and
$\sigma$ fixes $a,x_{0},x_{1},x_{14}$, $\sigma(x_{i})=x_{i+3}$ for $2\leq
i\leq 10$, and $\sigma(x_{i})=x_{i-9}$ for $11\leq i\leq 13$. By using a
composition of $\tau$ and $\sigma$, for $4\leq i\leq 14$, it is easy to obtain
a Hamilton cycle of $H_{16}^{\prime}-x_{i}$ which uses the spoke edge
$ax_{0}$, and hence not using $e$ or $e^{\prime}$. ∎

Figure 3. Cycles in hypohamiltonian graphs

We propose the following problem.

######  Problem 6.

Let $3\leq k<n$. Characterise the graphs $G\in\mathcal{F}_{k}$ of order $n$
with $crx_{k}(G)=e(G)$. In particular, when $k=n-1$, does there exist $G$ such
that $crx_{n-1}(G)=e(G)$, other than when $G$ is the cycle $C_{n}$, or $n=10$
and $G$ is the Petersen graph?

We conclude this section by comparing the parameters $crx_{k}(G)$ and
$rx_{k}(G)$. It is easy to see that for $k\geq 1$ and $G\in\mathcal{F}_{k}$,
we have $crx_{k}(G)>rx_{k}(G)$. Indeed, we may take a $k$-rainbow cycle
colouring of $G$ with $t=crx_{k}(G)\geq 3$ colours, and recolour all edges of
colour $t$ with colour $1$. In the new $(t-1)$-colouring, any $k$ vertices lie
on a rainbow path. Hence, $rx_{k}(G)\leq crx_{k}(G)-1$.

How close and how far apart can the parameters $crx_{k}(G)$ and $rx_{k}(G)$
be? In Theorem 7 below, we see that the difference $crx_{k}(G)-rx_{k}(G)$ can
be small (at most $3$) for infinitely many graphs, and can also be arbitrarily
large.

######  Theorem 7.

Let $k\geq 1$.

  1. (a)

There are infinitely many graphs $G$ such that

$crx_{k}(G)-rx_{k}(G)=\left\\{\begin{array}[]{l@{\quad}l}3,&\textup{\emph{if
$k=1$,}}\\\\[2.15277pt] 2,&\textup{\emph{if $k=2,3$,}}\\\\[2.15277pt]
1,&\textup{\emph{if $k\geq 4$.}}\end{array}\right.$

  2. (b)

For every $c\geq 1$, there exists a graph $G$ such that $rx_{k}(G)\leq
k^{2}-1$ and $crx_{k}(G)\geq c$. Hence, the difference $crx_{k}(G)-rx_{k}(G)$
can be arbitrarily large.

###### Proof.

(a) In Theorem 9 in Section 3, we will see that
$crx_{1}(K_{n})=crx_{2}(K_{n})=3$ for $n\geq 3$. Hence,
$crx_{1}(K_{n})-rx_{1}(K_{n})=3$ and $crx_{2}(K_{n})-rx_{2}(K_{n})=2$ for
$n\geq 3$.

A result of Chartrand et al. ([13], Theorem 2.1) states that
$rx_{3}(C_{n})=n-2$ for $n\geq 4$, and $rx_{k}(C_{n})=n-1$ for $4\leq k\leq
n$. Hence, $crx_{3}(C_{n})-rx_{3}(C_{n})=2$ for $n\geq 4$, and
$crx_{k}(C_{n})-rx_{k}(C_{n})=1$ for $4\leq k\leq n$.
(b) Let $P$ be a path on $k-1$ vertices, and $C$ be a cycle on $kt\geq 3$
vertices. Let $G=P+C$, the join of $P$ and $C$. Note that for $k=1$, $G$ is
the cycle $C_{t}$. Let $V(P)=\\{u_{0},\dots,u_{k-2}\\}$, and
$V(C)=\\{v_{0},v_{1},\dots,v_{kt-1}\\}$, with the indices of the vertices of
$C$ taken cyclically modulo $kt$. If $k=1$, then $crx_{1}(G)=t\geq c$ if $t$
is sufficiently large, and $rx_{1}(G)=0$. From now on, let $k\geq 2$.

First, let $S=\\{v_{0},v_{t},v_{2t}\dots,v_{(k-1)t}\\}$. It is easy to see
that any cycle of $G$ containing $S$ must contain the vertices
$v_{it},v_{it+1},\dots,v_{(i+1)t-1}$, for some $0\leq i\leq k-1$. Hence, we
have $crx_{k}(G)\geq t\geq c$ if $t$ is sufficiently large.

Now, define a colouring $\phi$ of $G$, using colours $0,1,2,\dots,k^{2}-2$, as
follows. For $0\leq i\leq kt-1$, let $0\leq\bar{i}\leq k-1$ be the integer
with $\bar{i}\equiv i$ (mod $k)$. For $0\leq j\leq k-2$, let
$\phi(u_{j}v_{i})=\bar{i}+jk$. For $0\leq j\leq k-3$, let
$\phi(u_{j}u_{j+1})=k^{2}-k+j$. Let $\phi(e)=k^{2}-2$ for every edge $e$ of
$C$. We claim that any $k$ vertices are connected by a rainbow tree. It
suffices to consider a set $S$ of $k$ vertices in $C$, and find a rainbow tree
$T$ containing $S$ and using all edges of $P$. Let $S_{1},\dots,S_{r}$ be the
sets $S\cap\\{v_{\ell k},v_{\ell k+1},\dots,v_{(\ell+1)k-1}\\}$ which are non-
empty, for $0\leq\ell\leq t-1$. Note that $1\leq r\leq k$. If $1\leq r\leq
k-1$, then we obtain $T$ by taking $P$ and adding the edges $u_{j}v_{i}$,
where $0\leq j\leq r-1$ and $v_{i}\in S_{j+1}$. If $r=k$, then we have
$|S_{1}|=\cdots=|S_{k}|=1$. We obtain $T$ by taking $P$, and adding the edge
from $u_{j}$ to $S_{j+1}$ for $0\leq j\leq k-2$. Let $S_{k-1}=\\{v_{a}\\}$ and
$S_{k}=\\{v_{b}\\}$. If $a\not\equiv b$ (mod $k)$, then we also add the edge
$u_{k-2}v_{b}$. If $a\equiv b$ (mod $k)$, then we also add the path
$v_{b}v_{b-1}u_{k-2}$ if $b\not\equiv 0$ (mod $k)$, or the path
$v_{b}v_{b+1}u_{k-2}$ if $b\equiv 0$ (mod $k)$. In every case, $T$ is a
suitable rainbow tree. Hence, $rx_{k}(G)\leq k^{2}-1$. ∎

##  3 Specific families of graphs

We will now compute $crx_{k}(G)$ for some specific graphs $G$. First, we
consider the case when $G$ is a wheel $W_{n}=C_{n}+v$, i.e., the graph on
$n+1\geq 4$ vertices, obtained by connecting the _centre_ vertex $v$ to all
vertices of the cycle $C_{n}$. Even though the connectivity of $W_{n}$ is only
$3$, we see that $crx_{k}(W_{n})$ is well-defined for every $k$ with $1\leq
k\leq n+1$, since $W_{n}$ is Hamiltonian.

######  Theorem 8.

  1. (a)

$crx_{1}(W_{n})=3$ for $n\geq 3$.

  2. (b)

$crx_{2}(W_{3})=3$, and $crx_{2}(W_{n})=\lceil\frac{n}{2}\rceil+2$ for $n\geq
4$.

  3. (c)

$crx_{3}(W_{n})=\left\\{\begin{array}[]{l@{\quad}l}n,&\textup{\emph{if $3\leq
n\leq 7$,}}\\\\[2.15277pt] n-1,&\textup{\emph{if $8\leq n\leq
11$,}}\\\\[2.15277pt] n-2,&\textup{\emph{if $n\geq 12$.}}\end{array}\right.$

  4. (d)

For $k\geq 4$ and $n+1\geq k$,

$crx_{k}(W_{n})=\left\\{\begin{array}[]{l@{\quad}l}n+1,&\textup{\emph{if
$n<2k$,}}\\\\[2.15277pt] n,&\textup{\emph{if $n\geq 2k$.}}\end{array}\right.$

###### Proof.

Throughout, let $W_{n}=C_{n}+v$, where $v$ is the centre of $W_{n}$. Let
$V^{\prime}=\\{v_{0},v_{1},\dots,v_{n-1}\\}$ be the vertex set of $C_{n}$,
where the vertices are in that order, with the indices taken modulo $n$. For a
set $I$ of consecutive vertices of $V^{\prime}$, where $2\leq|I|\leq n-1$, let
$C(I)$ be the cycle of $W_{n}$ with vertex set $I\cup\\{v\\}$. Let
$\bar{I}=V^{\prime}\setminus I$ and
$\bar{I}_{i}=V^{\prime}\setminus\\{v_{i}\\}$.
(a) It suffices to prove that $crx_{1}(W_{n})\leq 3$. Colour the edge $vv_{i}$
with colour $1$ if $i$ is odd, and colour $2$ if $i$ is even. Colour all edges
of $C_{n}$ with colour $3$. This is a rainbow cycle colouring for $W_{n}$,
since every vertex lies in a rainbow triangle.
(b) The colouring of $W_{3}$ where $vv_{i}$ and $v_{i+1}v_{i+2}$ have colour
$i$, for $i=1,2,3$, is a $2$-rainbow cycle colouring. Hence,
$crx_{2}(W_{3})=3$.

Let $n\geq 4$. We define a colouring $\phi$ on $W_{n}$ as follows. The cycle
$C_{n}$ uses colours $1,2,\dots,\lceil\frac{n}{2}\rceil$, where
$\phi(v_{i-1}v_{i})\equiv i$ (mod $\lceil\frac{n}{2}\rceil$). Let
$\phi(vv_{i})=\lceil\frac{n}{2}\rceil+1$ for $0\leq
i\leq\lceil\frac{n}{2}\rceil-1$, and $\phi(vv_{i})=\lceil\frac{n}{2}\rceil+2$
for $\lceil\frac{n}{2}\rceil\leq i\leq n-1$. Then, the cycles $C(I)$ where
$|I|=\lfloor\frac{n}{2}\rfloor+1$, except when $n$ is odd and
$I=\\{v_{0},\dots,v_{\lfloor n/2\rfloor}\\}$; and the cycle
$C(\\{v_{0},\dots,v_{\lceil n/2\rceil}\\})$, are all rainbow coloured. Any two
vertices of $W_{n}$ lie in one of these cycles. Hence, $\phi$ is a $2$-rainbow
cycle colouring, and $crx_{2}(W_{n})\leq\lceil\frac{n}{2}\rceil+2$.

Now, we prove that $crx_{2}(W_{n})\geq\lceil\frac{n}{2}\rceil+2$. The shortest
cycle in $W_{n}$ containing $v_{0}$ and $v_{\lfloor n/2\rfloor}$ has length
$\lfloor\frac{n}{2}\rfloor+2$. Hence
$crx_{2}(W_{n})\geq\lfloor\frac{n}{2}\rfloor+2$, and we are done for $n$ even.
Let $n\geq 5$ be odd. Suppose that there exists a $2$-rainbow cycle colouring
of $W_{n}$, using exactly
$\lfloor\frac{n}{2}\rfloor+2=\lceil\frac{n}{2}\rceil+1$ colours. For $0\leq
i\leq n-1$, the only shortest cycle in $W_{n}$ containing $v_{i}$ and
$v_{i+\lfloor n/2\rfloor}$ is $C(J_{i})$, where
$J_{i}=\\{v_{i},\dots,v_{i+\lfloor n/2\rfloor}\\}$. Hence every cycle
$C(J_{i})$ must be rainbow coloured, using every one of the
$\lfloor\frac{n}{2}\rfloor+2$ colours. By considering $C(J_{i})$ and
$C(J_{i-\lfloor n/2\rfloor})$, the only edge of $C_{n}$ that can possibly have
the same colour as $vv_{i}$ is $v_{i+\lfloor n/2\rfloor}v_{i+\lfloor
n/2\rfloor+1}$. Since $\lfloor\frac{n}{2}\rfloor+2<n$ for $n\geq 5$, assume
that there exist two edges $vv_{i}$ and $vv_{j}$ with colour $1$. Then, no
edge of $C_{n}$ has colour $1$. Since $vv_{i},vv_{i+\lfloor n/2\rfloor}\in
E(C(J_{i}))$ for all $0\leq i\leq n-1$, and $n$ is odd, there exists
$0\leq\ell\leq n-1$ such that $vv_{\ell}$ and $vv_{\ell+\lfloor n/2\rfloor}$
have different colours, and different from colour $1$. But then, $C(I_{\ell})$
contains an edge in $C_{n}$ using colour $1$, a contradiction. Hence,
$crx_{2}(W_{n})\geq\lceil\frac{n}{2}\rceil+2$.
(c) We have $crx_{3}(W_{3})=3$ by considering the same colouring of $W_{3}$ as
in (b). Let $n\geq 4$. We define a colouring $\phi$ on $W_{n}$ as follows.

  * •

For $4\leq n\leq 7$, colour the edges of $C_{n}$ with colours $1,\dots,n-2$ so
that $\phi(v_{i-1}v_{i})\equiv i$ (mod $n-2$). Let
$\phi(vv_{0})=\phi(vv_{1})=n-1$ and
$\phi(vv_{2})=\phi(vv_{n-2})=\phi(vv_{n-1})=n$. Let
$\mathcal{I}=\\{\\{v_{0}\\},\\{v_{1}\\},\\{v_{2},\dots,v_{n-2}\\},\\{v_{n-1}\\}\\}$.

  * •

For $8\leq n\leq 11$, let $\phi(v_{0}v_{1})=\phi(v_{4}v_{5})=1$,
$\phi(v_{2}v_{3})=\phi(v_{6}v_{7})=2$,
$\phi(vv_{i-2})=\phi(v_{i-1}v_{i})=\frac{i}{2}+2$ for $i=2,4,6,8$,
$\phi(v_{i}v_{i-1})=i-2$ for $9\leq i\leq n$, and $\phi(vv_{i})=n-1$ for
$i=1,3,5,7$. Let
$\mathcal{I}=\\{\\{v_{1},v_{2}\\},\\{v_{3},v_{4}\\},\\{v_{5},v_{6}\\},\\{v_{7},\dots,v_{n-1},v_{0}\\}\\}$.

  * •

For $n\geq 12$, let $\phi(v_{0}v_{1})=\phi(v_{6}v_{7})=1$,
$\phi(v_{3}v_{4})=\phi(v_{9}v_{10})=2$,
$\phi(vv_{i-2})=\phi(v_{i-1}v_{i})=\frac{2(i+1)}{3}+1$ for $i=2,5,8,11$,
$\phi(vv_{i+1})=\phi(v_{i-1}v_{i})=\frac{2i}{3}+2$ for $i=3,6,9$,
$\phi(vv_{1})=\phi(v_{11}v_{12})=10$, and $\phi(v_{i}v_{i-1})=i-2$ for $13\leq
i\leq n$ (if $n\geq 13$). Let $\mathcal{I}=\\{\\{v_{1},v_{2},v_{3}\\},$
$\\{v_{4},v_{5},v_{6}\\},\\{v_{7},v_{8},v_{9}\\},\\{v_{10},\dots,v_{n-1},v_{0}\\}\\}$.

In each case, let $S$ be a set of three vertices of $W_{n}$. Then $S\cap
I=\emptyset$ for some $I\in\mathcal{I}$. The cycle $C(\bar{I})$ is rainbow,
and contains $S$. Hence,

$crx_{3}(W_{n})\leq\left\\{\begin{array}[]{l@{\quad}l}n,&\textup{if $4\leq
n\leq 7$,}\\\\[2.15277pt] n-1,&\textup{if $8\leq n\leq 11$,}\\\\[2.15277pt]
n-2,&\textup{if $n\geq 12$.}\end{array}\right.$

Now, we prove the matching lower bounds for $crx_{3}(W_{n})$. Consider a
colouring of $W_{n}$, using fewer than $n$ colours for $4\leq n\leq 7$, and
fewer than $n-1$ colours for $8\leq n\leq 11$. Then two edges of $C_{n}$, say
$v_{0}v_{1}$ and $v_{i-1}v_{i}$ for some $2\leq
i\leq\lfloor\frac{n}{2}\rfloor+1$, have the same colour. Any cycle containing
the vertices $v_{0},v_{\lfloor n/4\rfloor+1},v_{\lfloor n/2\rfloor+1}$ cannot
be rainbow. Hence, $crx_{3}(W_{n})\geq n$ for $4\leq n\leq 7$, and
$crx_{3}(W_{n})\geq n-1$ for $8\leq n\leq 11$. Now let $n\geq 12$. Again, we
recall the result of Chartrand et al. ([13], Theorem 2.1) that
$rx_{3}(C_{n})=n-2$ for $n\geq 4$. If there exists a $3$-rainbow cycle
colouring of $W_{n}$, using fewer than $n-2$ colours, then by omitting the
edges $vv_{i}$, we obtain a colouring for $C_{n}$ which gives
$rx_{3}(C_{n})<n-2$, a contradiction. Hence, $crx_{3}(W_{n})\geq n-2$.
(d) Since $W_{n}$ is Hamiltonian, we have $crx_{k}(W_{n})\leq n+1$. For $n\geq
2k$, define a colouring $\phi$ on $W_{n}$ as follows. For $1\leq i\leq n$, let
$\phi(v_{i-1}v_{i})=i$. For $0\leq j\leq 2k-1$ with $k$ even, or $0\leq j\leq
2k-7$ with $k$ odd, let

$\phi(vv_{j})=\left\\{\begin{array}[]{l@{\quad}l}j+2,&\textup{if $j\equiv 0,1$
(mod $4$),}\\\\[2.15277pt] j-1,&\textup{if $j\equiv 2,3$ (mod
$4$).}\end{array}\right.$

In addition, for $k$ odd, let $\phi(vv_{2k-6})=\phi(vv_{2k-2})=2k-4$,
$\phi(vv_{2k-5})=\phi(vv_{2k-1})=2k-2$, $\phi(vv_{2k-4})=2k-5$, and
$\phi(vv_{2k-3})=2k-1$. We claim that $\phi$ is a $k$-rainbow cycle colouring.
Let $S$ be a set of $k$ vertices of $W_{n}$. If $v\not\in S$, then $C_{n}$ is
a rainbow cycle containing $S$. Now, let $v\in S$. For $k$ even, $S$ does not
contain some vertex of the set $\\{v_{j}:0\leq j\leq 2k-1$ and $j\equiv 1,2$
(mod $4)\\}$, say $v_{\ell}$. The cycle $C(\bar{I}_{\ell})$ contains $S$, and
is rainbow since we can obtain $C(\bar{I}_{\ell})$ from $C_{n}$ by deleting
and adding two edges with colours $\ell$ and $\ell+1$. For $k$ odd, $S$ does
not contain some vertex of the set $\\{v_{j}:0\leq j\leq 2k-7$ and $j\equiv
1,2$ (mod $4)\\}\cup\\{v_{2k-5},v_{2k-2}\\}$, or
$S\cap\\{v_{2k-4},v_{2k-3}\\}=\emptyset$. If the former happens then, again
letting $v_{\ell}$ be a vertex omitted by $S$, the cycle $C(\bar{I}_{\ell})$
contains $S$ and is rainbow. If the latter, then the cycle
$C(\overline{\\{v_{2k-4},v_{2k-3}\\}})$ contains $S$ and is rainbow, since to
obtain $C(\overline{\\{v_{2k-4},v_{2k-3}\\}})$ from $C_{n}$, we delete three
edges of colours $2k-4,2k-3,2k-2$, and add two edges of colours $2k-4$ and
$2k-2$. Hence, $crx_{k}(W_{n})\leq n$.

Now, we prove the matching lower bounds for $crx_{k}(W_{n})$. First, we show
that $crx_{k}(W_{n})\geq n$ for all $n$ with $n+1\geq k$. Suppose that there
exists a $k$-rainbow cycle colouring, using fewer than $n$ colours. Then two
edges $e_{1}$ and $e_{2}$ in $C_{n}$ have the same colour. Let $S$ be a set of
$k$ vertices which contains the three (if $e_{1}$ and $e_{2}$ are incident) or
four (otherwise) end-vertices of $e_{1}$ and $e_{2}$. Let $C$ be a rainbow
cycle containing $S$. Then $C$ must use exactly one of $e_{1}$ and $e_{2}$,
say $e_{2}$. Thus, $C$ must be the cycle obtained from $C_{n}$ by deleting
$e_{1}$, and adding the two edges connecting $v$ and the end-vertices of
$e_{1}$. But then, $C$ has length $n+1$, and so cannot be rainbow, a
contradiction.

We are done for $n\geq 2k$. Now, let $n<2k$. We show that $crx_{k}(W_{n})\geq
n+1$. This clearly holds for $k=n+1$. Thus, let $k\leq n$, so that $n\geq 4$.
Suppose that there exists a $k$-rainbow cycle colouring of $W_{n}$, using
fewer than $n+1$ colours. By the previous argument, such a colouring uses
exactly $n$ colours, and moreover, the $C_{n}$ must be rainbow coloured. We
will choose a set $S$ of $k$ vertices of $W_{n}$ such that $v\in S$, so that
any rainbow cycle containing $S$ has the form $C(I)$ for some $I\subset
V^{\prime}$. We say that a cycle $C(I)$ is _large_ if
$|I|\geq\lceil\frac{n}{2}\rceil+1$, and _small_ otherwise. A rainbow coloured
large cycle $C(I)$ is _maximal_ if there is no rainbow coloured cycle
$C(I^{\prime})$ such that $I^{\prime}\varsupsetneq I$. By considering $S$ such
that $v,v_{0},v_{\lfloor n/2\rfloor},v_{\lfloor n/2\rfloor+1}\in S$, we see
that there must exist a rainbow coloured large cycle, and hence a maximal
cycle. Let $C(I_{1}),\dots,C(I_{p})$ be all the maximal cycles, for some
$p\geq 1$. Now, for two maximal cycles $C(I_{i})$ and $C(I_{j})$, the sets
$\bar{I}_{i}$ and $\bar{I}_{j}$ are not nested, i.e., neither one contains the
other. For $1\leq i\leq p$, let $v_{h_{i}}\in\bar{I}_{i}$ be the “first
vertex” of $\bar{I}_{i}$, i.e., if $\bar{I}_{i}=\\{v_{q},v_{q+1},\dots\\}$ for
some $0\leq q\leq n-1$, then $h_{i}=q$. We may assume that
$0=h_{1}<h_{2}<\cdots<h_{p}\leq n-1$. Next, since $C_{n}$ is rainbow coloured
and there are exactly $n$ colours, every edge $vv_{i}$ can belong to at most
one of $C(I_{1}),\dots,C(I_{p})$. Indeed, for the edge $vv_{0}$, the only
possible maximal cycle containing $vv_{0}$, if it exists, is either
$C(\\{v_{0},\dots,v_{s}\\})$ for some $\lceil\frac{n}{2}\rceil\leq s\leq n-2$,
or $C(\\{v_{t},\dots,v_{n-1},v_{0}\\})$ for some $2\leq
t\leq\lfloor\frac{n}{2}\rfloor$. A similar argument holds for any other edge
$vv_{i}$. It follows that $p\leq\lfloor\frac{n}{2}\rfloor\leq k-1$.

We say that the distinct vertices $u_{1},\dots,u_{p}$ are _representing
vertices_ for $\bar{I}_{1},\dots,\bar{I}_{p}$ if $u_{i}\in\bar{I}_{i}$ for
$1\leq i\leq p$. Since $v_{h_{1}},\dots,v_{h_{p}}$ are representing vertices
for $\bar{I}_{1},\dots,\bar{I}_{p}$, there exists at least one such set of
vertices. Let $S$ be a set of $k$ vertices with $v,u_{1},\dots,u_{p}\in S$. If
there is a large rainbow cycle containing $S$, then $S\subset V(C(I_{i}))$ for
some $1\leq i\leq p$. But this implies $u_{i}\in V(C(I_{i}))$, a
contradiction. Hence, it suffices to show that we can choose a set $S$ of $k$
vertices, containing $v$ and representing vertices for
$\bar{I}_{1},\dots,\bar{I}_{p}$, so that no small rainbow cycle can contain
$S$.
_Case 1._ $1\leq p\leq k-2$.
If $p=1$, then recall that $v_{0}\in\bar{I}_{1}$. Let $S$ be such that
$v,v_{0},v_{\lfloor n/2\rfloor},$ $v_{\lfloor n/2\rfloor+1}\in S$. If $2\leq
p\leq k-2$, choose a set of representing vertices $u_{1},\dots,u_{p}$ for
$\bar{I}_{1},\dots,\bar{I}_{p}$. We may assume that $u_{1}=v_{0}$ and
$u_{2}=v_{i}$ where $1\leq i\leq\lfloor\frac{n}{2}\rfloor$. We further choose
$v_{\lfloor n/2\rfloor+1}$ (if it is not already among the $u_{j}$), so that
$v,u_{1},u_{2},\dots,u_{p},v_{\lfloor n/2\rfloor+1}\in S$. In every case,
there is no small cycle containing $S$.
_Case 2._ $p=k-1$.
We have $p=\lfloor\frac{n}{2}\rfloor$, and $n=2k-2$ or $n=2k-1$. We claim
that, we can choose the representing vertices $u_{1},\dots,u_{p}$ for
$\bar{I}_{1},\dots,\bar{I}_{p}$, so that they do not form a set of consecutive
vertices of $V^{\prime}$. For $1\leq i\leq p$, let $u_{i}=v_{h_{i}}$. If
$u_{1},\dots,u_{p}$ are consecutive vertices of $V^{\prime}$, then we have
$u_{i}=v_{i-1}$ for all $1\leq i\leq p=k-1$. Note that $u_{p}=v_{k-2}$, and we
must have $v_{k-1}\in\bar{I}_{p}$. Otherwise, we have
$\bar{I}_{p}=\\{v_{k-2}\\}$, and since $\bar{I}_{1},\dots,\bar{I}_{p}$ are
pairwise non-nested, it is easy to see that we have
$\bar{I}_{i}=\\{v_{i-1}\\}$ for all $1\leq i\leq p$. But this is a
contradiction, since $C(I_{1})$ and $C(I_{3})$ would both contain the edge
$vv_{1}$. Thus, we may replace $u_{p}=v_{k-2}$ with $u_{p}=v_{k-1}$. We then
have $u_{1},\dots,u_{p}$ is a set of representing vertices for
$\bar{I}_{1},\dots,\bar{I}_{p}$ which is not a set of consecutive vertices of
$V^{\prime}$, since $k-1\leq n-2$, so that $u_{p}=v_{k-1}$ is not adjacent to
$v_{0}$ in $C_{n}$.

Now let $S=\\{v,u_{1},\dots,u_{p}\\}$. If $n=2k-2$, then $S$ is not contained
in a small cycle, since this would require the $u_{j}$ to be consecutive
vertices of $V^{\prime}$. Let $n=2k-1$ and suppose that there is a small cycle
containing $S$. We may assume that $u_{1}=v_{0}$, $u_{p}=v_{k-1}$, and
$u_{2},\dots,u_{p-1}\in\\{v_{1},\dots,v_{k-2}\\}$, so that the only small
cycle containing $S$ is $C=C(\\{v_{0},\dots,v_{k-1}\\})$. The edges $vv_{0}$
and $vv_{k-1}$ are in $C$, and we may assume that $vv_{0}$ is contained in a
maximal cycle $C^{*}$, so that $C^{*}=C(\\{v_{\ell},\dots,v_{n-1},v_{0}\\})$
for some $2\leq\ell\leq k-1$ (since if $C^{*}$ contains $S$, then again we
obtain a contradiction). It follows that the colour of $vv_{0}$ is the same as
one of $v_{0}v_{1},\dots,v_{\ell-1}v_{\ell}$, and thus $C$ is not a rainbow
cycle.
We conclude that we can always find a set $S$ of $k$ vertices so that no
rainbow cycle contains $S$, which is the required contradiction. Hence
$crx_{k}(W_{n})\geq n+1$, as required. ∎

Our next task is to determine $crx_{k}(G)$ when $G=K_{n}$ is a complete graph.
We have the following result.

######  Theorem 9.

  1. (a)

$crx_{1}(K_{n})=crx_{2}(K_{n})=3$ for $n\geq 3$.

  2. (b)

For $k\geq 3$, there exists $N=N(k)$ such that for $n\geq N$, we have
$crx_{k}(K_{n})=2k-1$.

###### Proof.

(a) It suffices to show that $crx_{2}(K_{n})\leq 3$ for every $n\geq 3$. We
use induction on $n$ to show that there is a $2$-rainbow cycle colouring of
$K_{n}$, using three colours. For $n=3$, we take the rainbow coloured $K_{3}$.
Let $n\geq 4$, and $u$ be a vertex of $G=K_{n}$. By induction, there exists a
$2$-rainbow cycle colouring $\phi^{\prime}$ for $G-u\cong K_{n-1}$, using
three colours. Define a colouring $\phi$ for $G$, using three colours, as
follows. If $n-1$ is odd, take $x_{1},x_{2},x_{3}\in V(G-u)$ such that
$\phi^{\prime}(x_{1}x_{2})$, $\phi^{\prime}(x_{2}x_{3})$ and
$\phi^{\prime}(x_{3}x_{1})$ are distinct, and let
$\phi(ux_{i})=\phi^{\prime}(x_{i+1}x_{i+2})$ for $i=1,2,3$ (with indices taken
modulo $3$). Then (whether $n-1$ is odd or even), take a perfect matching $M$
on the remaining vertices of $G-u$, and for $vw\in M$, let $\phi(uv)$ and
$\phi(uw)$ be the two colours different from $\phi^{\prime}(vw)$. Now, any two
vertices $x,y\in V(G)$ lie in a rainbow triangle under $\phi$, where we use
induction if $x,y\in V(G-u)$. Hence, $\phi$ is a $2$-rainbow cycle colouring
of $G$, and we are done by induction.
(b) Recall that for integers $r,\ell\geq 1$, the _Ramsey number_ $R_{r}(\ell)$
is the minimum integer $t$ such that, whenever we have an edge-colouring of
$K_{t}$ with at most $r$ colours, there exists a monochromatic copy of
$K_{\ell}$. It is well-known that all Ramsey numbers $R_{r}(\ell)$ exist. If
$n\geq R_{2k-2}(k)$ and we have a $(2k-2)$-colouring of $K_{n}$, then there
exists a monochromatic copy of $K_{k}$, say with vertex set $S$. Any cycle of
length at most $2k-2$ containing $S$ must contain at least two edges with end-
vertices in $S$, and so cannot be rainbow. Hence, $crx_{k}(K_{n})\geq 2k-1$.

Now, we prove that $crx_{k}(K_{n})\leq 2k-1$ for $n$ sufficiently large.
Consider a random $(2k-1)$-colouring of $K_{n}$. For $S\subset V(K_{n})$ with
$|S|=k$, let $E_{S}$ be the event that there is no rainbow cycle containing
$S$. We estimate the probability $\mathbb{P}(E_{S})$. Let
$U_{1},\dots,U_{t}\subset V(K_{n})\setminus S$ be disjoint sets with
$t=\lfloor\frac{n-k}{k-1}\rfloor$, and $|U_{i}|=k-1$ for $1\leq i\leq t$. Let
$H$ be the complete subgraph of $K_{n}$ induced by $S$. Let $\Phi$ be the set
of all $(2k-1)$-colourings of $H$ with no rainbow cycle $C_{k}$ containing
$S$. Let $H$ be coloured by $\phi\in\Phi$ and $1\leq i\leq t$. There is at
least one way to colour the $k(k-1)$ edges of $E(S,U_{i})$ so that we have a
rainbow cycle containing $S$, with vertices in $S\cup U_{i}$. Indeed, if
$S=\\{v_{1},\dots,v_{k}\\}$ and $U_{i}=\\{u_{1},\dots,u_{k-1}\\}$, then we can
assign $2k-1$ distinct colours to the cycle $C=v_{1}u_{1}\cdots
v_{k-1}u_{k-1}v_{k}v_{1}$, since $v_{1}v_{k}$ is the only edge of $H$ in $C$.
Hence, there are some $\alpha_{\phi}<(2k-1)^{k(k-1)}$ colourings of
$E(S,U_{i})$ so that there is no rainbow cycle containing $S$, with vertices
in $S\cup B_{i}$. Let
$\alpha=\max\\{\alpha_{\phi}:\phi\in\Phi\\}<(2k-1)^{k(k-1)}$. Since there are
at most $k(k-2)+{n-k\choose 2}$ edges not in
$E(H)\cup\bigcup_{i=1}^{t}E(S,U_{i})$, we have

$\mathbb{P}(E_{S})\leq\frac{|\Phi|\alpha^{t}(2k-1)^{k(k-2)+{n-k\choose
2}}}{(2k-1)^{n\choose
2}}\leq\frac{\gamma_{k}\alpha^{n/(k-1)}}{(2k-1)^{kn}}=\gamma_{k}^{\phantom{n}\\!}\delta_{k}^{n}=o(n^{-k}),$

where $\gamma_{k}>0$ and $0<\delta_{k}<1$ are constants depending only on $k$.
By the union bound,

$\mathbb{P}\bigg{(}\bigcup_{S\subset
V(K_{n}),\,|S|=k}E_{S}\bigg{)}\leq\sum_{S\subset
V(K_{n}),\,|S|=k}\mathbb{P}(E_{S})\leq{n\choose k}o(n^{-k})<1,$

for $n$ sufficiently large. Hence, there exists a $k$-rainbow cycle colouring
of $K_{n}$, using $2k-1$ colours, and $crx_{k}(K_{n})\leq 2k-1$. ∎

Remark. We may similarly prove the result that $rx_{k}(K_{n})=k$ for $n$
sufficiently large. This result is a special case of a conjecture of Chartrand
et al. ([13], Conjecture 3.12), and the conjecture itself has since been
solved by Cai et al. [12].
Next we consider $crx_{k}(G)$, when $G=K_{m,n}$ is a complete bipartite graph
with $2\leq m\leq n$. A sufficient condition for the existence of
$crx_{k}(K_{m,n})$ is $m\geq k$. We have the following result.

######  Theorem 10.

  1. (a)

$crx_{1}(K_{m,n})=4$ for $2\leq m\leq n$.

  2. (b)

    1. (i)

$crx_{2}(K_{2,n})=2n$ for $n\geq 2$.

    2. (ii)

$crx_{2}(K_{3,n})=r$ for $n\geq 36$, where $r$ is the integer such that
${r-1\choose 3}<n\leq{r\choose 3}$. Thus,
$crx_{2}(K_{3,n})=\sqrt[3]{6n}+C_{n}$, where $1<C_{n}<3$.

    3. (iii)

$crx_{2}(K_{m,n})=8$ for $m\geq 4$ and $n>7^{m}$.

  3. (c)

Let $k\geq 2$.

    1. (i)

$\lceil\frac{n}{k-1}\rceil\leq crx_{k}(K_{k,n})\leq kn$ for $n\geq k$.

    2. (ii)

$crx_{k}(K_{m,n})\geq 4k$ for $m\geq 2k$ and $n>(k-1)(4k-1)^{m}$.

    3. (iii)

$crx_{k}(K_{m,n})\leq 6k$ for $3k\leq m\leq n$.

###### Proof.

Throughout this proof, let $U$ and $V$ be the classes of $K_{m,n}$, with
$U=\\{u_{1},\dots,u_{m}\\}$ and $V=\\{v_{1},\dots,v_{n}\\}$. For integers
$1\leq\ell\leq N$, let $[N]=\\{1,\dots,N\\}$, and let $[N]^{(\ell)}$ denote
the family of all subsets of $[N]$ with size $\ell$.
(a) Clearly $crx_{1}(K_{m,n})\geq g(K_{m,n})=4$. Now, define a $4$-colouring
$\phi$ on $K_{m,n}$ where $\phi(u_{1}v_{1})=1$; $\phi(u_{1}w)=2$ for $w\in
V\setminus\\{v_{1}\\}$; $\phi(v_{1}w)=3$ for $w\in U\setminus\\{u_{1}\\}$; and
$\phi(xy)=4$ for $x\in U\setminus\\{u_{1}\\}$, $y\in V\setminus\\{v_{1}\\}$.
Then, every vertex of $K_{m,n}$ is in a rainbow cycle of length $4$ which uses
$u_{1}v_{1}$. Hence, $crx_{1}(K_{m,n})\leq 4$.
(b)(i) Since $K_{2,n}$ is minimally $2$-connected for $n\geq 2$, we have
$crx_{2}(K_{2,n})=e(K_{2,n})=2n$ by Theorem 4(b). It is also not difficult to
prove this result directly.
(b)(ii) Note that $n\geq 36$ implies $r\geq 8$. First, suppose that we have a
colouring of $K_{3,n}$, using at most $r-1$ colours. Let the colours be
$1,2,\dots,r-1$. For $x\in V$, let $A_{x}\in[r-1]^{(3)}$ be a set which
contains the colours incident with $x$. Since $n>{r-1\choose 3}$, there exist
$x,y\in V$ with $A_{x}=A_{y}$, and we cannot have $x$ and $y$ in a rainbow
cycle. Thus, $crx_{2}(K_{3,n})\geq r$.

Now, we define an $r$-colouring $\phi$ of $K_{3,n}$ as follows. Let
$U=\\{u_{1},u_{2},u_{3}\\}$ and $V^{\prime}=\\{v_{1},v_{2},v_{3}\\}\subset V$.
Let $\phi(u_{1}v_{3})=\phi(u_{2}v_{1})=\phi(u_{3}v_{2})=r-1$,
$\phi(u_{1}v_{2})=\phi(u_{2}v_{3})=\phi(u_{3}v_{1})=r$, and
$\phi(u_{i}v_{i})=r-5+i$ for $i=1,2,3$. For $1\leq\ell\leq r$, the
_colexicographic ordering_ on the elements of $[r]^{(\ell)}$ is a linear
ordering where an $\ell$-set $A=\\{a_{1},\dots,a_{\ell}\\}$ with
$a_{1}<\cdots<a_{\ell}$ precedes an $\ell$-set $B=\\{b_{1},\dots,b_{\ell}\\}$
with $b_{1}<\cdots<b_{\ell}$ if $a_{m}<b_{m}$, where $m=\max\\{p:a_{p}\neq
b_{p}\\}$. We label the $n-3$ vertices of $V\setminus V^{\prime}$ with the
$n-3$ initial members of $[r]^{(3)}$ in the colexicographic ordering. If a
vertex $v\in V\setminus V^{\prime}$ has been labelled with
$\\{a_{1},a_{2},a_{3}\\}$ where $1\leq a_{1}<a_{2}<a_{3}\leq r$, then we let
$\phi(u_{i}v)=a_{i}$ for $i=1,2,3$. For $v\in V$, let $A_{v}$ be the $3$-set
consisting of the colours at $v$. Note that the vertices of $V^{\prime}$ have
been labelled with the last three members of $[r]^{(3)}$ in the
colexicographic ordering, and since $n\leq{r\choose 3}$, the $3$-sets $A_{v}$
are distinct over all $v\in V$.

We claim that $\phi$ is a $2$-rainbow cycle colouring. Firstly, it is easy to
verify that any two vertices of $U\cup V^{\prime}$ lie in a rainbow $C_{4}$.
Next, let $x\in V$ and $y\in V\setminus V^{\prime}$. If $|A_{x}\cup
A_{y}|\in\\{5,6\\}$, then clearly $x$ and $y$ lie in a rainbow $C_{4}$. Thus,
let $A_{x}=\\{a,b,c\\}$ and $A_{y}=\\{a,b,d\\}$, where $a,b,c,d\in[r]$ are
distinct. If $x$ and $y$ are not in a rainbow $C_{4}$, then there exists a
rainbow path of length four in the form $u_{\alpha}xu_{\gamma}yu_{\beta}$,
where $\\{\alpha,\beta,\gamma\\}=\\{1,2,3\\}$, and using the colours
$a,b,c,d$. This can be seen easily by considering the two edges of colours $c$
and $d$, and whether or not they are incident. It then suffices to find a
vertex $w\in V\setminus\\{x,y\\}$ such that
$\phi(wu_{\alpha}),\phi(wu_{\beta})\not\in\\{a,b,c,d\\}$, so that $x$ and $y$
are in a rainbow $C_{6}$. If $a,b,c,d\leq r-2$, then $x,y\in V\setminus
V^{\prime}$, and we can choose $w=v_{\gamma}$, so that
$\\{\phi(wu_{\alpha}),\phi(wu_{\beta})\\}=\\{r-1,r\\}$. Otherwise, suppose
that at least one of $a,b,c,d$ is at least $r-1$. If $x\in V^{\prime}$, then
two of $a,b,c$ are $r-1$ and $r$, so that at least one of $a,b,d$, the colours
at $y$, is $r-1$ or $r$. It follows that there exists $z\in V\setminus
V^{\prime}$ (either $z=x$ or $z=y$) such that $A_{z}$ contains $r-1$ or $r$.
This implies that all members of $[r-2]^{(3)}$ are present among the $3$-sets
labelling the vertices of $V\setminus V^{\prime}$, since $[r-2]^{(3)}$ forms
an initial segment in the colexicographic ordering, and a $3$-set containing
$r-1$ or $r$ succeeds every $3$-set in $[r-2]^{(3)}$ in the ordering. Since
$r-2\geq 6$, we can choose a suitable vertex $w\in V\setminus V^{\prime}$ such
that $A_{w}\in[r-2]^{(3)}$ and $A_{w}\subset[r-2]\setminus\\{a,b,c,d\\}$.

Finally, let $x\in U$ and $y\in V\setminus V^{\prime}$. We choose $w\in
V\setminus V^{\prime}$ by choosing the $3$-set $A_{w}$ as follows. If
$A_{y}=\\{1,2,3\\}$, then let $A_{w}=\\{1,2,4\\}$. If
$A_{y}=\\{a,b,c\\}\neq\\{1,2,3\\}$ where $1\leq a<b<c\leq r$, then let
$A_{w}=\\{a-1,b,c\\}$ if $a\geq 2$; or $A_{w}=\\{a,b-1,c\\}$ if $a=1$ and
$b\geq 3$; or $A_{w}=\\{a,b,c-1\\}$ if $a=1$, $b=2$ and $c\geq 4$. Note that
$A_{w}$ exists among the $3$-sets labelling $V\setminus V^{\prime}$ since
$A_{w}$ precedes $A_{y}=\\{a,b,c\\}$ in the colexicographic ordering. Then $y$
and $w$ are not in a rainbow $C_{4}$. Hence by the previous argument, $y$ and
$w$ lie in a rainbow $C_{6}$, which thus contains $x$ and $y$.

Therefore, $\phi$ is a $2$-rainbow cycle colouring for $K_{3,n}$, and we have
$crx_{2}(K_{3,n})\leq r$.
(b)(iii) We have $crx_{2}(K_{m,n})\geq 8$ for $m\geq 4$ and $n>7^{m}$ from
(c)(ii) below. We prove that $crx_{2}(K_{m,n})\leq 8$ for $n\geq m\geq 4$.
Define an $8$-colouring $\phi$ of $K_{m,n}$ as follows. Let
$V^{\prime}=\\{v_{1},v_{2},v_{3}\\}\subset V$, and assign to these vertices
the $m$-vectors $\vec{v}_{1}=(4,3,2,1,1,\dots,1)$,
$\vec{v}_{2}=(5,6,7,8,8,\dots,8)$ and $\vec{v}_{3}=(8,7,6,5,5,\dots,5)$. For
every $v_{j}\in V\setminus V^{\prime}$, assign the $m$-vector
$\vec{v}_{j}=(1,2,3,4,4,\dots,4)$. For $v_{j}\in V$, let
$\phi(u_{i}v_{j})=\vec{v}_{ji}$ for $1\leq i\leq m$. We claim that $\phi$ is a
$2$-rainbow cycle colouring for $K_{m,n}$. Let
$U^{\prime}=\\{u_{1},u_{2},u_{3}\\}\subset U$, and $x,y\in V(K_{m,n})$. We
find a rainbow cycle containing $x$ and $y$. If $x\in U^{\prime}$ and $y\in
U$, we take $xv_{1}yv_{2}x$. If $x,y\in U\setminus U^{\prime}$, we take
$xwu_{2}v_{1}yv_{2}u_{3}v_{3}x$ for some $w\in V\setminus V^{\prime}$. If
$x\in V^{\prime}$ and $y\in V$, we take $xu_{1}yu_{2}x$. If $x,y\in V\setminus
V^{\prime}$, we take $xu_{2}v_{2}u_{3}yu_{4}v_{3}u_{1}x$. Finally, if $x\in U$
and $y\in V$, then first choose $w\in U^{\prime}\setminus\\{x\\}$, and note
that the path $xyw$ is rainbow and uses colours either in $\\{1,2,3,4\\}$ or
$\\{5,6,7,8\\}$. If the former, we can take $xywv_{2}x$ (note that $y\neq
v_{2}$), and if the latter, we can take $xywv_{1}x$ (note that $y\neq v_{1}$).
Hence, $crx_{2}(K_{m,n})\leq 8$.
(c)(i) Let $n\geq k$. Clearly, we have $crx_{k}(K_{k,n})\leq e(K_{k,n})=kn$.
Now, suppose that we have a colouring of $K_{m,n}$, using fewer than
$\lceil\frac{n}{k-1}\rceil$ colours. We may assume that
$u_{1}v_{1},\dots,u_{1}v_{k}$ have the same colour. Letting
$S=\\{v_{1},\dots,v_{k}\\}$, any cycle of $K_{k,n}$ containing $S$ must have
the vertex set $U\cup S$, and so cannot be rainbow. Hence,
$crx_{k}(K_{k,n})\geq\lceil\frac{n}{k-1}\rceil$.
(c)(ii) Let $m\geq 2k$ and $n>(k-1)(4k-1)^{m}$. Let $\phi$ be a
$(4k-1)$-colouring of $K_{m,n}$, using the colours $1,2,\dots,4k-1$. For
$v_{j}\in V$, let $\vec{v}_{j}$ be the $m$-vector where
$\vec{v}_{ji}=\phi(u_{i}v_{j})$ for $1\leq i\leq m$. Then the lower bound on
$n$ implies that, there exists a set of vertices $S\subset V$ with $|S|=k$,
whose members are all assigned with the same $m$-vector. If there exists a
rainbow cycle $C$ containing $S$, then in $C$, the distance between any two
vertices of $S$ is at least $4$. Thus, $C$ has length at least $4k$, and so
cannot be rainbow, a contradiction. Hence, $crx_{k}(K_{m,n})\geq 4k$.
(c)(iii) Let $3k\leq m\leq n$. We define a $6k$-colouring $\phi$ of $K_{m,n}$
as follows. Let $U^{\prime}=\\{u_{1},\dots,u_{2k}\\}\subset U$ and
$V^{\prime}=\\{v_{1},\dots,v_{2k}\\}\subset V$. For $v_{j}\in V^{\prime}$, we
assign the $2k$-vector $\vec{v}_{j}=(2k-j+2,\dots,2k,1,2,\dots,2k-j+1)$, and
let $\phi(u_{i}v_{j})=\vec{v}_{ji}$ for $u_{i}\in U^{\prime}$. For $u_{i}\in
U\setminus U^{\prime}$ and $v_{j}\in V^{\prime}$, let $\phi(u_{i}v_{j})=2k+j$.
For $u_{i}\in U^{\prime}$ and $v_{j}\in V\setminus V^{\prime}$, let
$\phi(u_{i}v_{j})=4k+j$. The edges $u_{i}v_{j}\in E(U\setminus
U^{\prime},V\setminus V^{\prime})$ are coloured arbitrarily with used colours.

We claim that $\phi$ is a $k$-rainbow cycle colouring for $K_{m,n}$. Note that
the vertices of $U\setminus U^{\prime}$ are indistinguishable, and likewise
for the vertices of $V\setminus V^{\prime}$. Thus, it suffices to consider the
subgraph $H$ of $K_{m,n}$ induced by $U^{\prime}\cup U^{\prime\prime}\cup
V^{\prime}\cup V^{\prime\prime}$, where
$U^{\prime\prime}=\\{u_{2k+1},\dots,u_{3k}\\}$ and
$V^{\prime\prime}=\\{v_{2k+1},\dots,v_{3k}\\}$. Consider the edge set

$F=\\{u_{2i-1}v_{i}:1\leq i\leq k\\}\cup\\{u_{2i}v_{k+i}:1\leq i\leq
k-1\\}\cup\\{u_{k}v_{2k}\\}.$

The edges of $F$ are rainbow coloured, since the colours of the edges in the
three sets are $1,2,\dots,k$; $k+2,k+3,\dots,2k$; and $k+1$. Moreover, they
almost form a perfect matching between $U^{\prime}$ and $V^{\prime}$: the
edges $u_{k}v_{3k/2}$ (resp. $u_{k}v_{\lceil k/2\rceil}$) and $u_{k}v_{2k}$
are incident at $u_{k}$ for $k$ even (resp. odd), and the remaining edges are
independent. Now, let $S\subset V(H)$ with $|S|=k$. We may assume that $S\cap
V^{\prime\prime}\subset\\{v_{2k+1},\dots,v_{3k-1}\\}$, since the colouring
$\phi$ restricted to $H$ has the same structure under the symmetry between the
two classes of $H$; and $u_{2k}\not\in S$, since otherwise we may consider a
shift of $F$. Relabelling the edges of $F$ as
$\tilde{u}_{1}\tilde{v}_{1},\dots,\tilde{u}_{2k-2}\tilde{v}_{2k-2},u_{k}\tilde{v}_{2k-1},u_{k}v_{2k}$,
we obtain a rainbow cycle containing $S$ by connecting the edges
$u_{2k+i}\tilde{v}_{2i}$, $u_{2k+i}\tilde{v}_{2i+1}$,
$v_{2k+i}\tilde{u}_{2i-1}$ and $v_{2k+i}\tilde{u}_{2i}$ for $1\leq i\leq k-1$,
and $u_{3k}\tilde{v}_{1}$ and $u_{3k}v_{2k}$. Hence, $crx_{k}(K_{m,n})\leq
6k$. ∎

We now consider $crx_{k}(G)$ when $G$ is a complete multipartite graph. For
$t\geq 2$, let $K_{n_{1},\dots,n_{t}}$ be the complete $t$-partite graph with
class sizes $1\leq n_{1}\leq\cdots\leq n_{t}$. Let $K_{t\times n}$ be the
balanced complete $t$-partite graph, where each class has $n$ vertices. We
have the following result.

######  Theorem 11.

  * (a)

$crx_{1}(K_{n_{1},\dots,n_{t}})=3$ for $t\geq 3$ and $1\leq
n_{1}\leq\cdots\leq n_{t}$.

  * (b)

For $k,t\geq 2$, there exists $N=N(k,t)$ such that for $n\geq N$, we have
$crx_{k}(K_{t\times n})=2k$.

###### Proof.

(a) It suffices to prove that $crx_{1}(K_{n_{1},\dots,n_{t}})\leq 3$. By
Theorem 9(a), there exists a rainbow cycle colouring $\phi$ of $K_{t}$, using
three colours. We may obtain a rainbow cycle colouring of
$K_{n_{1},\dots,n_{t}}$ with three colours by taking a blow-up of $\phi$,
where the $i$th vertex of $K_{t}$ is replaced with a vertex set of size
$n_{i}$, for $1\leq i\leq t$.
(b) Let $V_{1},\dots,V_{t}$ be the classes of $K_{t\times n}$, with
$|V_{i}|=n$ for $1\leq i\leq t$. If $n\geq k$, then we have
$crx_{k}(K_{t\times n})\geq 2k$, since any cycle containing $k$ vertices of
$V_{1}$ has length at least $2k$.

We prove that $crx_{k}(K_{t\times n})\leq 2k$ for $n$ sufficiently large.
Consider a random $2k$-colouring of $K_{t\times n}$. For $S\subset
V(K_{t\times n})$ with $|S|=k$, let $E_{S}$ be the event that there is no
rainbow cycle containing $S$. We estimate the probability $\mathbb{P}(E_{S})$.
For $1\leq i\leq t$, let $X_{i}=S\cap V_{i}$, where indices involving $i$ are
taken modulo $t$ throughout. Let $s_{i}=|S\cap V_{i}|$, so that
$s_{1}+\cdots+s_{t}=k$. Let $1\leq q\leq t$ be the number of the $s_{i}$ that
are non-zero. We may assume that $s_{1}\geq\cdots\geq s_{q}\geq 1$. For $2\leq
i\leq q+1$, let $Y_{i1},\dots,Y_{ih}\subset V_{i}\setminus X_{i}$ be disjoint
sets with $h=\lfloor\frac{n-s_{2}}{s_{1}}\rfloor$, and $|Y_{ij}|=s_{i-1}$ for
all $1\leq j\leq h$. We may find such sets $Y_{ij}$ since
$(\frac{n-s_{2}}{s_{1}})s_{i-1}\leq n-s_{i}$ for every $2\leq
i\leq\min(q+1,t)$, and $(\frac{n-s_{2}}{s_{1}})s_{t}\leq n-s_{1}$ if $q=t$ and
$n\geq k$, so that

$|Y_{i1}|+\cdots+|Y_{ih}|=hs_{i-1}\leq\Big{(}\frac{n-s_{2}}{s_{1}}\Big{)}s_{i-1}\leq
n-s_{i}=|V_{i}\setminus X_{i}|.$

Define the subgraph $H=\bigcup_{i=1}^{q-1}[X_{i},X_{i+1}]$. Let $\Phi$ be the
set of all $2k$-colourings of $H$ with no rainbow cycle $C_{k}$ containing
$S$. By convention, if $q=1$, we have $H$ is the empty graph on
$S=X_{1}\subset V_{1}$, and $\Phi$ consists of one trivial colouring. Let $H$
be coloured by $\phi\in\Phi$. For $1\leq j\leq h$, define the subgraph
$H_{j}=[X_{1},X_{2}\cup Y_{2j}]\cup[X_{q}\cup
Y_{qj},Y_{q+1,j}]\cup\bigcup_{i=2}^{q-1}[X_{i}\cup Y_{ij},X_{i+1}\cup
Y_{i+1,j}]$, where $H_{j}=[X_{1},Y_{2j}]$ if $q=1$. There is at least one way
to colour the edges of $E(H_{j})\setminus E(H)$ so that we have a rainbow
cycle containing $S$, with vertices in $V(H_{j})$. Indeed, if $q=1$, choose a
spanning cycle of $H_{j}=[X_{1},Y_{2j}]$ and assign $2k$ distinct colours to
it. Let $2\leq q\leq t$. For $1\leq i\leq q$, choose a spanning path of
$[X_{i},Y_{i+1,j}]$ with end-vertices $x_{i}\in X_{i}$ and $y_{i+1}\in
Y_{i+1,j}$. Then, add the edges
$u_{1}u_{2},v_{2}u_{3},\dots,v_{q-1}u_{q},v_{q}v_{q+1}$. We have a spanning
cycle $C$ of $H_{j}$ where $u_{1}u_{2}$ is the only edge of $H$ in $C$, and
thus we may assign $2k$ distinct colours to $C$. Hence, there are some
$\alpha_{\phi}<(2k)^{e(H_{j})-e(H)}=(2k)^{e(H_{1})-e(H)}$ colourings of
$E(H_{j})\setminus E(H)$ so that there is no rainbow cycle containing $S$,
with vertices in $V(H_{j})$. Let
$\alpha=\max\\{\alpha_{\phi}:\phi\in\Phi\\}<(2k)^{e(H_{1})-e(H)}$. Since there
are ${tn\choose 2}-e(H)-(e(H_{1})-e(H))h$ edges not in
$\bigcup_{j=1}^{h}E(H_{j})$, we have

$\mathbb{P}(E_{S})\leq\frac{|\Phi|\alpha^{h}(2k)^{{tn\choose
2}-e(H)-(e(H_{1})-e(H))h}}{(2k)^{tn\choose
2}}\leq\frac{\alpha^{h}}{(2k)^{(e(H_{1})-e(H))h}}=o(n^{-k}).$

By the union bound,

$\mathbb{P}\bigg{(}\bigcup_{S\subset V(K_{t\times
n}),\,|S|=k}E_{S}\bigg{)}\leq\sum_{S\subset V(K_{t\times
n}),\,|S|=k}\mathbb{P}(E_{S})\leq{tn\choose k}o(n^{-k})<1,$

for $n$ sufficiently large. Hence, there exists a $k$-rainbow cycle colouring
of $K_{t\times n}$, using $2k$ colours, and $crx_{k}(K_{t\times n})\leq 2k$. ∎

In Theorems 10 and 11, we were only able to determine or estimate $crx_{k}(G)$
for some values of $k$ and some complete bipartite or multipartite graphs $G$.
In particular, for fixed $k$ and $m$, and $n$ sufficiently large, we see that
$crx_{k}(K_{k,n})=\Theta_{n}(n)$, and $crx_{k}(K_{m,n})=O_{n}(1)$ for $m\geq
3k$. We pose the following problem.

######  Problem 12.

Let $k\geq 2$

  1. (a)

For $2\leq m\leq n$, determine $crx_{k}(K_{m,n})$ for the cases not covered by
Theorems 10 and 11. For fixed $k$ and $m$, what is the behaviour of
$crx_{k}(K_{m,n})$ for $k\leq m\leq 3k$ and large $n$?

  2. (b)

For $t\geq 3$ and $1\leq n_{1}\leq\cdots\leq n_{t}$, determine
$crx_{k}(K_{n_{1},\dots,n_{t}})$ for the cases not covered by Theorem 11.

We conclude this section by considering $crx_{k}(G)$ where $G=Q_{n}$ is the
$n$-dimensional discrete binary cube. That is, $V(Q_{n})$ consists of all
$n$-vectors $v=(v_{1},\dots,v_{n})$ with $v_{i}\in\\{0,1\\}$ for $1\leq i\leq
n$, and for $u,v\in V(Q_{n})$, we have $uv\in E(Q_{n})$ if and only if $u$ and
$v$ differ at exactly one coordinate. Note that $Q_{n}$ is an $n$-regular
graph with $2^{n}$ vertices and $2^{n-1}n$ edges. If $n=p+q$, then $Q_{n}$ can
be considered as a blow-up of $Q_{q}$, with each vertex of $Q_{q}$ replaced by
a copy of $Q_{p}$, and an edge of $Q_{q}$ is replaced by a matching that
matches the corresponding vertices of $Q_{p}$. We write $Q_{n}=Q_{p}\oplus
Q_{q}$, and for $v\in V(Q_{n})$, we write $v=\hat{v}\oplus\tilde{v}$, where
$\hat{v}\in V(Q_{p})$ and $\tilde{v}\in V(Q_{q})$ are the vectors containing
the first $p$ and the last $q$ coordinates of $v$.

Since $Q_{n}$ is Hamiltonian for $n\geq 2$, the parameter $crx_{k}(Q_{n})$ is
defined for all $1\leq k\leq 2^{n}$ and $n\geq 2$. In the following result, we
determine $crx_{k}(Q_{n})$ exactly for small and large $k$.

######  Theorem 13.

Let $n\geq 2$.

  1. (a)

$crx_{1}(Q_{n})=4$.

  2. (b)

$crx_{2}(Q_{n})=crx_{3}(Q_{n})=2n$.

  3. (c)

$crx_{k}(Q_{n})=2^{n}$ for $2^{n-1}\leq k\leq 2^{n}$.

###### Proof.

(a) Clearly $crx_{1}(Q_{2})=4$. Let $n\geq 3$. We have $crx_{1}(Q_{n})\geq
g(Q_{n})=4$. Since $Q_{n}=Q_{2}\oplus Q_{n-2}$, we have a rainbow cycle
colouring of $Q_{n}$ with four colours where each of the $2^{n-2}$ copies of
$Q_{2}$ is given a rainbow colouring. Hence, $crx_{1}(Q_{n})\leq 4$.
(b) It suffices to prove that $crx_{2}(Q_{n})\geq 2n$ and $crx_{3}(Q_{n})\leq
2n$. We have $crx_{2}(Q_{n})\geq 2n$, since the shortest cycle containing the
vertices $(0,\dots,0)$ and $(1,\dots,1)$ has length $2n$. To prove that
$crx_{3}(Q_{n})\leq 2n$, we construct a $3$-rainbow cycle colouring of
$Q_{n}$, using $2n$ colours. We proceed inductively. For $n=2$, we give
$Q_{2}$ a rainbow colouring with colours $1,2,3,4$. Let $n\geq 3$, and suppose
that we have constructed a $3$-rainbow cycle colouring $\phi^{\prime}$ of
$Q_{n-1}$, using the colours $1,\dots,2(n-1)$. We have $Q_{n}=Q_{n-1}\oplus
Q_{1}$, and for $v\in Q_{n}$, we have $v=\hat{v}\oplus\tilde{v}$, where
$\hat{v}\in V(Q_{n-1})$ and $\tilde{v}\in V(Q_{1})$. Let $Q_{n-1}^{-}$ and
$Q_{n-1}^{+}$ be the copies of $Q_{n-1}$ containing the vertices $v\in
V(Q_{n})$ with $\tilde{v}=(0)$ and $\tilde{v}=(1)$, respectively. Define the
colouring $\phi$ of $Q_{n}$, with colours $1,\dots,2n$, as follows. For $uv\in
E(Q_{n})$, let

$\phi(uv)=\left\\{\begin{array}[]{ll}\phi^{\prime}(\hat{u}\hat{v}),&\textup{if
}\tilde{u}=\tilde{v},\\\\[4.30554pt] 2n-1,&\displaystyle\textup{if
}\hat{u}=\hat{v},\,\tilde{u}\neq\tilde{v}\textup{, and
}\sum\hat{u}_{i}=\sum\hat{v}_{i}\equiv 0\textup{ (mod }2),\\\\[4.30554pt]
2n,&\displaystyle\textup{if }\hat{u}=\hat{v},\,\tilde{u}\neq\tilde{v}\textup{,
and }\sum\hat{u}_{i}=\sum\hat{v}_{i}\equiv 1\textup{ (mod
}2).\end{array}\right.$

We claim that $\phi$ is a $3$-rainbow cycle colouring for $Q_{n}$. Let
$x,y,z\in V(Q_{n})$. If $x,y,z\in V(Q_{n-1}^{-})$ or $x,y,z\in
V(Q_{n-1}^{+})$, then by induction, $x,y$ and $z$ lie in a rainbow cycle. Now
by the symmetry between $Q_{n-1}^{-}$ and $Q_{n-1}^{+}$, assume that $x,y\in
V(Q_{n-1}^{-})$ and $z\in V(Q_{n-1}^{+})$. Let $x_{+},y_{+}\in V(Q_{n-1}^{+})$
and $z_{-}\in V(Q_{n-1}^{-})$ where $x_{+}=\hat{x}\oplus(1)$,
$y_{+}=\hat{y}\oplus(1)$ and $z_{-}=\hat{z}\oplus(0)$. By induction, there are
rainbow cycles $C_{-}\subset Q_{n-1}^{-}$ and $C_{+}\subset Q_{n-1}^{+}$ such
that, $C_{-}=a_{1}a_{2}\cdots a_{t}a_{1}$, $C_{+}=b_{1}b_{2}\cdots b_{t}b_{1}$
for some $t\geq 4$; $\hat{a}_{p}=\hat{b}_{p}$ and
$\phi(a_{p}a_{p+1})=\phi(b_{p}b_{p+1})\in\\{1,\dots,2(n-1)\\}$ for every
$1\leq p\leq t$, where indices referring to $C_{-},C_{+}$ are taken modulo $t$
throughout; and $x,y,z_{-}\in V(C_{-})$ and $x_{+},y_{+},z\in V(C_{+})$, with
$(x,y,z_{-})=(a_{i},a_{j},a_{\ell})$ and
$(x_{+},y_{+},z)=(b_{i},b_{j},b_{\ell})$, where we may assume that $1\leq
i\leq\ell<j\leq t$. Let $P\subset C_{-}$ be the $y-x$ path $a_{j}a_{j+1}\cdots
a_{i}$, and $R\subset C_{+}$ be the $x_{+}-y_{+}$ path $b_{i}b_{i+1}\cdots
b_{j}$. Note that $z\in V(R)$. If
$\\{\phi(xx_{+}),\phi(yy_{+})\\}=\\{2n-1,2n\\}$, we have the rainbow cycle
$xx_{+}Ry_{+}yPx$. If $\phi(xx_{+})=\phi(yy_{+})=2n-1$ or $2n$, then consider
the vertices $a_{j-1}$ and $b_{j-1}$. Note that $a_{j-1}\neq x$ and
$b_{j-1}\neq x_{+}$, since $C_{-}$ and $C_{+}$ have length at least $4$, and
$\phi(xx_{+})=\phi(yy_{+})$ means that $x$ and $y$ are not neighbours in
$C_{-}$, and $x_{+}$ and $y_{+}$ are not neighbours in $C_{+}$. Also, we have
$\\{\phi(xx_{+}),\phi(a_{j-1}b_{j-1})\\}=\\{2n-1,2n\\}$. We have the rainbow
cycle $xx_{+}Rb_{j-1}a_{j-1}yPx$.

Hence, $\phi$ is a $3$-rainbow cycle colouring for $Q_{n}$ with $2n$ colours,
and we are done by induction.
(c) Let $2^{n-1}\leq k\leq 2^{n}$. Clearly we have $crx_{k}(Q_{n})\leq 2^{n}$
since $Q_{n}$ is Hamiltonian. Now, $Q_{n}$ is a balanced bipartite graph with
classes $V_{0}$ and $V_{1}$, where $V_{0}$ (resp. $V_{1}$) consists of the
$2^{n-1}$ vertices at even (resp. odd) distance from $(0,\dots,0)$. Let $S$ be
a set of $k$ vertices containing $V_{0}$. Then, every cycle of $Q_{n}$
containing $S$ must have length $2^{n}$. Hence, $crx_{k}(Q_{n})\geq 2^{n}$. ∎

For $4\leq k<2^{n-1}$, the exact determination of $crx_{k}(Q_{n})$ appears to
be more difficult. In the following result, we give a partial answer to this
problem, by showing that $crx_{k}(Q_{n})$ is linear in $n$, for fixed $k\geq
4$ and $n$ sufficiently large.

######  Theorem 14.

Let $k\geq 4$ and $n\geq 4k^{2}$. Then there exist constants $c_{k},C_{k}>0$
(depending only on $k$) such that

$c_{k}n\leq crx_{k}(Q_{n})\leq C_{k}n.$ (1)

Thus, we have $crx_{k}(Q_{n})=\Theta_{n}(n)$.

Before we prove Theorem 14, we gather some tools in order to enable us to
prove the upper bound. A graph $G$ is _$k$ -linked_ if $|V(G)|\geq 2k$, and
for every sequence $s_{1},\dots,s_{k},t_{1},\dots,t_{k}$ of distinct vertices
in $G$, there exist disjoint paths $P_{1},\dots,P_{k}$ such that the end-
vertices of $P_{i}$ are $s_{i}$ and $t_{i}$, for $1\leq i\leq k$. Clearly, a
$k$-linked graph is also $k$-connected, but the converse is not true. Jung
[25], and Larman and Mani [27], showed that there exists a function $f(k)$
such that every $f(k)$-connected graph is $k$-linked, and it was shown in [27]
that $f(k)=2^{3k\choose 2}+2k$. Bollobás and Thomason [10] then made a
significant improvement, when they proved that the result holds for
$f(k)=22k$. Thomas and Wollan [32] further improved this to $f(k)=10k$.

######  Theorem 15 ([32], Corollary 1.3).

If $G$ is a $10k$-connected graph, then $G$ is k-linked.

Let $S=(v_{1},\dots,v_{k})$ be an ordered $k$-tuple of vertices in a graph
$G$, where repetitions are permitted for the vertices. That is,
$S=(v_{1},\dots,v_{k})\in V(G)^{k}$. An _$S$ -subdivided closed walk_ is a
sequence $W=(v_{1},P_{1},v_{2},P_{2},v_{3},\dots,v_{k},P_{k},v_{1})$ such
that, $P_{i}$ is a $v_{i}-v_{i+1}$ path for $1\leq i\leq k$, and no two
$P_{i}$ and $P_{j}$ have an internal vertex in common. If $v_{i}=v_{i+1}$,
then $P_{i}$ is trivial, and if $v_{i}\neq v_{i+1}$, then $P_{i}$ has length
at least $2$. The indices of the vertices $v_{i}$ and the paths $P_{i}$ are
taken modulo $k$ throughout. By using the above result, we have the following
lemma, which says that for $Q_{n}$, if $n$ is sufficiently large, so that the
vertex connectivity of $Q_{n}$ is large, then $Q_{n}$ contains an
$S$-subdivided closed walk for every $S\in V(Q_{n})^{k}$.

######  Lemma 16.

Let $k\geq 4$ and $n\geq 11k$. Then for all ordered $k$-tuple
$S=(v_{1},\dots,v_{k})$ of vertices in $Q_{n}$, where repetitions of the
vertices are permitted in $S$, there exists an $S$-subdivided closed walk in
$Q_{n}$.

###### Proof.

Let $S=(v_{1},\dots,v_{k})\in V(Q_{n})^{k}$ be an ordered $k$-tuple, and
$u_{1},\dots,u_{\ell}$ be the distinct members of $S$, for some $1\leq\ell\leq
k$. Let $G=Q_{n}-\\{u_{1},\dots,u_{\ell}\\}$. It is well-known that the vertex
connectivity of $Q_{n}$ is $n$, and thus $G$ is $10k$-connected. By Theorem
15, $G$ is $k$-linked.

Now for $1\leq p\leq\ell$, let $m_{p}$ be the multiplicity of $u_{p}$ in $S$,
so that $\sum_{p=1}^{\ell}m_{p}=k$. Since $u_{p}$ has at least $10k$
neighbours in $Q_{n}$ lying in $V(G)$, we can choose disjoint sets
$U_{1},\dots,U_{\ell}\subset V(G)$ such that $|U_{p}|=2m_{p}$, and all
vertices of $U_{p}$ are neighbours of $u_{p}$ in $Q_{n}$, for $1\leq
p\leq\ell$. We choose distinct vertices
$s_{1},t_{1},\dots,s_{k},t_{k}\in\bigcup_{p=1}^{\ell}U_{p}$ as follows. For
$1\leq i\leq k$, let $v_{i}=u_{p}$ and $v_{i+1}=u_{q}$, and choose $s_{i}\in
U_{p}$, $t_{i}\in U_{q}$. This can be done, since a vertex $u_{p}$ is
considered exactly $2m_{p}=|U_{p}|$ times as we consider all consecutive pairs
$(v_{i},v_{i+1})$. Since $G$ is $k$-linked, we have disjoint paths
$L_{1},\dots,L_{k}$ in $G$ such that $L_{i}$ connects $s_{i}$ and $t_{i}$ for
$1\leq i\leq k$. Define the paths $P_{1},\dots,P_{k}$ as follows. For $1\leq
i\leq k$, if $v_{i}=v_{i+1}$, then $P_{i}$ is trivial. Otherwise, if
$v_{i}\neq v_{i+1}$, then let $P_{i}=v_{i}s_{i}L_{i}t_{i}v_{i+1}$, and note
that $P_{i}$ has length at least $3$. Then,
$(v_{1},P_{1},\dots,v_{k},P_{k},v_{1})$ is an $S$-subdivided closed walk in
$Q_{n}$, as required. ∎

We are now ready to prove Theorem 14.

###### Proof of Theorem 14.

We first prove the upper bound of (1). Set $K=11k$. We show that the upper
bound holds for $n\geq K=11k$ and $C_{k}=2^{2K-1}=2^{22k-1}$. We prove the
stronger assertion that there exists a colouring of $Q_{n}$, using at most
$C_{k}n$ colours, such that for every ordered $k$-tuple of vertices
$S=(v_{1},\dots,v_{k})\in V(Q_{n})^{k}$, there exists a rainbow $S$-subdivided
closed walk $W$. Thus in particular, if $v_{1},\dots,v_{k}$ are distinct, then
$W$ is a rainbow cycle that visits $v_{1},\dots,v_{k}$, in that order.

Let $n=aK+b$, where $a\geq 1$ and $0\leq b<K$. It suffices to construct the
required colouring of $Q_{n}$, using at most $C_{k}aK$ colours. We use
induction on $a$. For $a=1$, we have $n=K+b$, and $e(Q_{n})\leq
e(Q_{2K-1})=2^{2K-2}(2K-1)<C_{k}K$. Thus, we may use a rainbow colouring for
$Q_{n}$, and the strong assertion holds by Lemma 16. Now, let $n=aK+b$ with
$a\geq 2$, and suppose that the strong assertion holds for $Q_{(a-1)K+b}$ and
$Q_{K}$. We have $Q_{aK+b}=Q_{(a-1)K+b}\oplus Q_{K}$. By the induction
hypothesis, there exist colourings $\eta$ on $Q_{(a-1)K+b}$ and $\theta$ on
$Q_{K}$, using at most $C_{k}(a-1)K$ and $C_{k}K$ colours respectively, and
each colouring satisfies the strong assertion. We define the colouring $\phi$
on $Q_{aK+b}$, using at most $C_{k}aK$ colours, as follows. Let $uv\in
E(Q_{aK+b})$, with $u=\hat{u}\oplus\tilde{u}$ and $v=\hat{v}\oplus\tilde{v}$,
where $\hat{u},\hat{v}\in V(Q_{(a-1)K+b})$ and $\tilde{u},\tilde{v}\in
V(Q_{K})$. Let

$\phi(uv)=\left\\{\begin{array}[]{ll}\eta(\hat{u}\hat{v}),&\textup{if
}\hat{u}\hat{v}\in E(Q_{(a-1)K+b})\textup{ and }\tilde{u}=\tilde{v},\\\
\theta(\hat{u}\hat{v}),&\textup{if }\hat{u}=\hat{v}\textup{ and
}\tilde{u}\tilde{v}\in E(Q_{K}).\end{array}\right.$

The colour sets used by $\eta$ and $\theta$ are disjoint. Thus, $\phi$ uses at
most $C_{k}aK$ colours. We claim that $\phi$ is a colouring of $Q_{aK+b}$ that
satisfies the strong assertion. Let $S=(v_{1},\dots,v_{k})\in
V(Q_{aK+b})^{k}$, with $\hat{S}=(\hat{v}_{1},\dots,\hat{v}_{k})\in
V(Q_{(a-1)K+b})^{k}$ and $\tilde{S}=(\tilde{v}_{1},\dots,\tilde{v}_{k})\in
V(Q_{K})^{k}$, where $\hat{v}_{i}\oplus\tilde{v}_{i}=v_{i}$ for $1\leq i\leq
k$. By induction, there is a rainbow $\hat{S}$-subdivided closed walk
$\hat{W}$ in $Q_{(a-1)K+b}$ under $\eta$, and a rainbow $\tilde{S}$-subdivided
closed walk $\tilde{W}$ in $Q_{K}$ under $\theta$. Let
$\hat{W}=(\hat{v}_{1},L_{1},\dots,\hat{v}_{k},L_{k},\hat{v}_{1})$ and
$\tilde{W}=(\tilde{v}_{1},M_{1},\dots,\tilde{v}_{k},M_{k},\tilde{v}_{1})$. Now
for consecutive vertices $v_{i}$ and $v_{i+1}$, where $1\leq i\leq k$, we
define the $v_{i}-v_{i+1}$ path $P_{i}$ in $Q_{aK+b}$, as follows.

  * •

If $v_{i}=v_{i+1}$, then $P_{i}$ is trivial.

  * •

If $v_{i}\neq v_{i+1}$, with $\hat{v}_{i}=\hat{v}_{i+1}$, then let $P_{i}$ be
the copy of $M_{i}$ that connects $v_{i}$ and $v_{i+1}$. Note that $P_{i}$ has
length at least $2$.

  * •

Let $v_{i}\neq v_{i+1}$, with $\hat{v}_{i}\neq\hat{v}_{i+1}$. Then $L_{i}$ has
length at least $2$. There exist copies of $L_{i}$ within the copies of
$Q_{(a-1)K+b}$ that contain $v_{i}$ and $v_{i+1}$. Let $L^{\prime}$ and
$L^{\prime\prime}$ be these two copies of $L_{i}$. Let $u$ be an internal
vertex of $L_{i}$, and $u^{\prime},u^{\prime\prime}$ be the copies of $u$ in
$L^{\prime}$ and $L^{\prime\prime}$. Let $M$ be the copy of $M_{i}$ that
connects $u^{\prime}$ and $u^{\prime\prime}$. Note that if $v_{i}$ and
$v_{i+1}$ lie in the same copy of $Q_{(a-1)K+b}$, i.e.,
$\tilde{v}_{i}=\tilde{v}_{i+1}$, then $L^{\prime}=L^{\prime\prime}$,
$u^{\prime}=u^{\prime\prime}$, and $M$ is trivial. Let
$P_{i}=v_{i}L^{\prime}u^{\prime}Mu^{\prime\prime}L^{\prime\prime}v_{i+1}$,
which has length at least $2$.

Now, let $W=(v_{1},P_{1},\dots,v_{k},P_{k},v_{1})$. Then $W$ uses exactly the
colours of $\hat{W}$ and $\tilde{W}$, so $W$ is rainbow coloured in $Q_{aK+b}$
under $\phi$. We claim that the paths $P_{i}$ are pairwise internally vertex-
disjoint. It suffices to consider two paths of the type as described in the
third item above. Let
$P_{i}=v_{i}L^{\prime}u^{\prime}Mu^{\prime\prime}L^{\prime\prime}v_{i+1}$ and
$P_{j}=v_{j}L^{\ast}u^{\ast}Nu^{\ast\ast}L^{\ast\ast}v_{j+1}$ be two such
paths, for some $1\leq i<j\leq k$ with $v_{i}\neq v_{j}$. By considering the
first $(a-1)K+b$ coordinates of the vertices of
$V(v_{i}L^{\prime}u^{\prime}\cup
u^{\prime\prime}L^{\prime\prime}v_{i+1})\setminus\\{v_{i},v_{i+1}\\}$ and
$V(v_{j}L^{\ast}u^{\ast}\cup
u^{\ast\ast}L^{\ast\ast}v_{j+1})\setminus\\{v_{j},v_{j+1}\\}$, we obtain the
internal vertices of $L_{i}$ and $L_{j}$, so these two sets of vertices are
disjoint. By considering the last $K$ coordinates of the internal vertices of
$M$ and $N$, we see that these two sets are disjoint, since we obtain the
internal vertices of $M_{i}$ and $M_{j}$. Similarly,
$V(v_{i}L^{\prime}u^{\prime}\cup
u^{\prime\prime}L^{\prime\prime}v_{i+1})\setminus\\{v_{i},v_{i+1}\\}$ is
disjoint from the set of internal vertices of $N$, since the last $K$
coordinates of any vertex in the former set is either $\tilde{v}_{i}$ or
$\tilde{v}_{i+1}$, while those of any vertex in the latter set are neither.
The claim follows, and hence $W$ is a rainbow $S$-subdivided closed walk in
$Q_{aK+b}$. This completes the induction step for the strong assertion, and
the proof of the upper bound of (1).

Now, for the lower bound of (1), we prove that $crx_{k}(Q_{n})>\frac{kn}{2}$
for $n\geq 4k^{2}$. We find $k$ vertices in $Q_{n}$ such that the distance
between every pair is greater than $\frac{n}{2}$. Then the shortest cycle
containing the $k$ vertices has length greater than $\frac{kn}{2}$, and the
assertion follows. Let $k^{\prime}=2^{\lceil\log_{2}k\rceil}\geq 4$, the
smallest power of $2$ that is at least $k$. A _Hadamard matrix_ is a $q\times
q$ $(-1,1)$-matrix such that any two column vectors are orthogonal.
Equivalently, for any two column vectors $x$ and $y$, the number of
coordinates where $x$ and $y$ agree equals the number of coordinates where $x$
and $y$ differ. The famous _Hadamard conjecture_ states that whenever $q$ is a
multiple of $4$, then there exists a $q\times q$ Hadamard matrix. We employ
_Sylvester’s construction_ , which gives the existence of a Hadamard matrix
for every $q$ that is a power of $2$. The construction is given by the
following recursion.

$H_{1}=(1),\textup{ and }H_{2^{t}}=\begin{pmatrix}H_{2^{t-1}}&H_{2^{t-1}}\\\
H_{2^{t-1}}&-H_{2^{t-1}}\end{pmatrix}\textup{ for }t\geq 1.$

Consider the $k^{\prime}\times k^{\prime}$ Hadamard matrix $H_{k^{\prime}}$.
Every entry in the first row is a $1$. Delete the first row of
$H_{k^{\prime}}$, replace every $-1$ with a $0$, and take $k$ of the
$k^{\prime}$ resulting column $(k^{\prime}-1)$-vectors, say
$c_{1},\dots,c_{k}$. Let
$A_{1}\,\dot{\cup}\,\cdots\,\dot{\cup}\,A_{k^{\prime}-1}$ be a partition of
$\\{1,\dots,n\\}$, where $|A_{j}|=\lfloor\frac{n}{k^{\prime}-1}\rfloor$ or
$|A_{j}|=\lceil\frac{n}{k^{\prime}-1}\rceil$ for every $1\leq j\leq
k^{\prime}-1$. Let $v_{1},\dots,v_{k}$ be the $n$-vectors where $v_{\ell
i}=c_{\ell j}$ for $1\leq\ell\leq k$, $1\leq i\leq n$, and $i\in A_{j}$. Any
two of $c_{1},\dots,c_{k}$ have exactly $\frac{k^{\prime}}{2}$ differing
coordinates, so the distance between any two of $v_{1},\dots,v_{k}$ is at
least $\frac{k^{\prime}}{2}\lfloor\frac{n}{k^{\prime}-1}\rfloor>\frac{n}{2}$,
since $n\geq 4k^{2}>(k^{\prime}-1)^{2}$. Thus, any cycle of $Q_{n}$ containing
$v_{1},\dots,v_{k}$ has length greater than $\frac{kn}{2}$.

Therefore, both inequalities of (1) hold for $n\geq 4k^{2}$. The proof of
Theorem 14 is complete. ∎

Remark. Many other problems concerning the existence of rainbow cycles in
edge-coloured discrete binary cubes have also been considered. A result of
Faudree et al. [20] states that, for $n\geq 4$, $n\neq 5$, there exists an
edge-colouring of $Q_{n}$ with $n$ colours such that, every copy of $C_{4}$ is
rainbow. Since such an edge-colouring of $Q_{n}$ must be proper, $n$ colours
are also necessary. This result was extended by Mubayi and Stading [30]. They
proved that for $\ell\equiv 0$ (mod $4$), there exists an edge-colouring of
$Q_{n}$ with $\Theta_{n}(n^{\ell/4})$ colours such that, every copy of
$C_{\ell}$ is rainbow, and moreover, $\Theta_{n}(n^{\ell/4})$ colours are also
necessary. These may be considered as edge-chromatic number type results, and
they appear to be closely related to our problem of the determination of
$crx_{k}(Q_{n})$.
In Theorem 14, we have only determined the correct order of magnitude of
$crx_{k}(Q_{n})$ for fixed $k$ and large $n$, and we have made no serious
attempt to optimise the lower bound on $n$ (in terms of $k$), or the terms
$c_{k}$ and $C_{k}$. We have $c_{k}=\frac{k}{2}$ and $C_{k}=2^{22k-1}$, so the
gap between $c_{k}$ and $C_{k}$, when considered as a function of $k$, is very
large. It would be desirable to reduce this large gap. We leave the
determination of $crx_{k}(Q_{n})$ as an open problem.

######  Problem 17.

For $n\geq 4$, determine $crx_{k}(Q_{n})$ for every $4\leq k<2^{n-1}$.

## Acknowledgement

Henry Liu is partially supported by the Startup Fund of One Hundred Talent
Program of SYSU, National Natural Science Foundation of China (No. 11931002),
and National Key Research and Development Program of China (No.
2020YFA0712500).

## References

  * [1] M. Albert, A.M. Frieze, B. Reed, Multicoloured Hamilton cycles, _Electron. J. Combin._ 2 (1995), #R10.
  * [2] R.E.L. Aldred, B.D. McKay, N.C. Wormald, Small hypohamiltonian graphs, _J. Combin. Math. Combin. Comput._ 23 (1997), 143–152.
  * [3] B. Alexeev, On lengths of rainbow cycles, _Electron. J. Combin._ 13 (2006), #R105.
  * [4] N. Alon, On a conjecture of Erdős, Simonovits, and Sós concerning anti-Ramsey theorems, _J. Graph Theory_ 7 (1983), 91–94.
  * [5] R.N. Ball, A. Pultr, P. Vojtěchovský, Colored graphs without colorful cycles, _Combinatorica_ 27 (2007), 407–427
  * [6] B. Bollobás, “Extremal Graph Theory”, Academic Press, London, 1978.
  * [7] B. Bollobás, “Modern Graph Theory”, Springer-Verlag, New York, 1998.
  * [8] B. Bollobás, G. Brightwell, Cycles through specified vertices, _Combinatorica_ 13 (1993), 147–155.
  * [9] B. Bollobás, A.J. Harris, List-colourings of graphs, _Graphs Combin._ 1 (1985), 115–127.
  * [10] B. Bollobás, A. Thomason, Highly linked graphs, _Combinatorica_ 16 (1996), 313–320.
  * [11] J.A. Bondy, L. Lovász, Cycles through specified vertices of a graph, _Combinatorica_ 1 (1981), 117–140.
  * [12] Q. Cai, X. Li, J. Song, Solutions to conjectures on the $(k,\ell)$-rainbow index of complete graphs, _Networks_ 62 (2013), 220–224.
  * [13] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, _Networks_ 55 (2010), 360–367.
  * [14] R. Diestel, “Graph Theory”, 5th ed., Springer-Verlag, New York, 2018.
  * [15] G.A. Dirac, Some theorems on abstract graphs, _Proc. London Math. Soc._ 2 (1952), 69–81.
  * [16] G.A. Dirac, $4$-chrome Graphen und vollständige $4$-Graphen, _Math. Nachr._ 22 (1960), 51–60.
  * [17] P. Erdős, J. Nešetřil, V. Rödl, Some problems related to partitions of edges of a graph, in: Graphs and other Combinatorial Topics, Teubner, Leipzig (1983), 54–63.
  * [18] P. Erdős, A.L. Rubin, H. Taylor, Choosability in graphs, in: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979), Congress. Numer. XXVI (1980), 125–157.
  * [19] P. Erdős, M. Simonovits, V.T. Sós, Anti-Ramsey theorems, in: A. Hajnal, R. Rado, V.T. Sós (eds), Infinite and Finite Sets, Vol. II, Proc. Coll. Keszthely, 1973, Colloquia Math. Soc. János Bolyai 10, North-Holland (1975), 633–643.
  * [20] R.J. Faudree, A. Gyárfás, L. Lesniak, R.H. Schelp, Rainbow coloring the cube, _J. Graph Theory_ 17 (1993), 607–612.
  * [21] A. Frieze, M. Krivelevich, On rainbow trees and cycles, _Electron. J. Combin._ 15 (2008), #R59.
  * [22] G. Hahn, C. Thomassen, Path and cycle sub-Ramsey numbers and an edge-colouring conjecture, _Discrete Math._ 62 (1986), 29–33.
  * [23] T.R. Jensen, B. Toft, “Graph Coloring Problems”, John Wiley & Sons, Inc., New York, 1995.
  * [24] T. Jiang, D.B. West, On the Erdős-Simonovits-Sós conjecture about the anti-Ramsey number of a cycle, _Combin. Probab. Comput._ 12 (2003), 585–598,
  * [25] H.A. Jung, Eine Verallgemeinerung des $n$-fachen Zusammenhangs für graphen, _Math. Ann._ 187 (1970), 95–103.
  * [26] P. Keevash, D. Mubayi, B. Sudakov, J. Verstraëte, Rainbow Turán problems, _Combin. Probab. Comput._ 16 (2007), 109–126.
  * [27] D.G. Larman, P. Mani, On the existence of certain configurations within graphs and the $1$-skeletons of polytopes, _Proc. London Math. Soc._ 20 (1970), 144–160.
  * [28] S. Li, Y. Shi, J. Tu, Y. Zhao, On the complexity of $k$-rainbow cycle colouring problems, _Discrete Appl. Math._ 264 (2019), 125–133.
  * [29] K. Menger, Zur allgemeinen Kurventheorie, _Fund. Math._ 10 (1927), 96–115.
  * [30] D. Mubayi, R. Stading, Coloring the cube with rainbow cycles, _Electron. J. Combin._ 20(2) (2013), #R4.
  * [31] J.J. Montellano-Ballesteros, V. Neumann-Lara, An anti-Ramsey theorem on cycles, _Graphs Combin._ 21 (2005), 343–354.
  * [32] R. Thomas, P. Wollan, An improved linear edge bound for graph linkages, _European J. Combin._ 26 (2005), 309–324
  * [33] V.G. Vizing, On an estimate of the chromatic class of a $p$-graph (in Russian), _Diskret. Analiz._ 3 (1964), 25–30.
  * [34] V.G. Vizing, Coloring the vertices of a graph in prescribed colors (in Russian), _Diskret. Analiz._ 29 (1976), 3–10.