# Notes on Aharoni’s rainbow cycle conjecture

Katie Clinch  ,  Jackson Goerner  ,  Tony Huynh  and  Freddie Illingworth
School of Computer Science and Engineering, UNSW, Sydney, Australia
<EMAIL_ADDRESS>School of Mathematics, Monash University, Melbourne,
Australia<EMAIL_ADDRESS>Dipartimento di Informatica, Sapienza
Università di Roma, Italy<EMAIL_ADDRESS>Mathematical Institute,
University of Oxford, Oxford, United Kingdom<EMAIL_ADDRESS>
###### Abstract.

In 2017, Ron Aharoni made the following conjecture about rainbow cycles in
edge-coloured graphs: If $G$ is an $n$-vertex graph whose edges are coloured
with $n$ colours and each colour class has size at least $r$, then $G$
contains a rainbow cycle of length at most $\lceil\frac{n}{r}\rceil$. One
motivation for studying Aharoni’s conjecture is that it is a strengthening of
the Caccetta-Häggkvist conjecture on digraphs from 1978.

In this article, we present a survey of Aharoni’s conjecture, including many
recent partial results and related conjectures. We also present two new
results. Our main new result is for the $r=3$ case of Aharoni’s conjecture. We
prove that if $G$ is an $n$-vertex graph whose edges are coloured with $n$
colours and each colour class has size at least $3$, then $G$ contains a
rainbow cycle of length at most $\frac{4n}{9}+7$. We also discuss how our
approach might generalise to larger values of $r$.

Research of F.I. supported by EPSRC grant EP/V007327/1. Research of T.H. was
supported by the Australian Research Council.

##  1\. Introduction

In 1978, Caccetta and Häggkvist made the following conjecture about directed
cycles in digraphs.

######  Conjecture 1.1 (Caccetta-Häggkvist).

For all positive integers $n,r$, every simple111A digraph is _simple_ if for
all vertices $u$ and $v$, there is at most one arc from $u$ to $v$. $n$-vertex
digraph with minimum outdegree at least $r$ contains a directed cycle of
length at most $\lceil\frac{n}{r}\rceil$.

Despite considerable effort from numerous researchers, the Caccetta-Häggkvist
conjecture remains open. A complete summary of the plethora of results related
to the Caccetta-Häggkvist is beyond the scope of this survey. We refer the
interested reader to Sullivan [22] for a brief synopsis. We instead focus on
the following generalisation of Conjecture 1.1.

######  Conjecture 1.2 (Aharoni).

Let $G$ be a simple222An edge-coloured graph $G$ is _simple_ if each colour
class does not contain parallel edges. edge-coloured graph with $n$ vertices
and $n$ colours, where each colour class has size at least $r$. Then $G$
contains a rainbow333A subgraph of an edge-coloured graph is _rainbow_ if no
two of its edges are the same colour. cycle of length at most
$\lceil\frac{n}{r}\rceil$.

For completeness, we now give a proof that Conjecture 1.2 indeed implies
Conjecture 1.1. In fact, as noted in [9], the following weakening of Aharoni’s
conjecture already implies the Caccetta-Häggkvist conjecture.

######  Conjecture 1.3 (DeVos et al. [9]).

Let $G$ be a simple edge-coloured graph with $n$ vertices and $n$ colours,
where each colour class has size at least $r$. Then $G$ contains a cycle $C$
of length at most $\lceil\frac{n}{r}\rceil$ such that no two incident edges of
$C$ are the same colour.

###### Proof of Conjecture 1.1, assuming Conjecture 1.3.

Let $D$ be a simple digraph with $n$ vertices and minimum outdegree at least
$r$. Let $G$ be the graph obtained from $D$ by forgetting the orientations of
all arcs. Colour $uv\in E(G)$ with colour $u$ if $(u,v)\in E(D)$. Clearly,
this colouring uses $|V(D)|=n$ colours. Moreover, since $D$ has minimum
outdegree at least $r$, each colour class has size at least $r$. Therefore, by
Conjecture 1.3, $G$ contains a properly edge-coloured cycle $C$ of length at
most $\lceil\frac{n}{r}\rceil$. The set of arcs in $D$ corresponding to the
edges of $C$ must be a directed cycle; otherwise $C$ is not properly edge-
coloured. ∎

Despite the fact that Aharoni’s conjecture implies the Caccetta-Häggkvist
conjecture, a proof of Aharoni’s conjecture may be easier to find than a proof
of the Caccetta-Häggkvist conjecture. Although this might sound
counterintuitive, the method of proving a stronger statement is very common in
combinatorics. For example, Thomassen [23] found a beautiful short proof that
every planar graph is 5-colourable by proving a stronger list colouring
version of the theorem. Moreover, generalisation often leads to new techniques
and new questions which one would not even consider in the original setting.
We will see that this is the case for Aharoni’s conjecture in the next
section.

##  2\. Related Results and Conjectures

In this section, we survey results and conjectures related to rainbow cycles.
For a general survey on rainbow sets, we refer the reader to Aharoni and
Briggs [2].

###  2.1. Larger Colour Classes

Much of the research on the Caccetta-Häggkvist conjecture has focused on the
directed triangle case ($r=\lceil\frac{n}{3}\rceil$). A natural strategy is to
increase the outdegree condition until one can prove the existence of a
directed triangle. The best result in this direction is the following result
of Hladký et al. [12], which uses the flag algebra machinery developed by
Razborov [19].

######  Theorem 2.1.

Every simple $n$-vertex digraph with minimum outdegree at least $0.3465n$
contains a directed triangle.

Similarly, for Aharoni’s conjecture, one can ask how large must the colour
classes be to ensure a rainbow cycle of length at most
$\lceil\frac{n}{r}\rceil$? The first non-trivial bound was proven by Hompe et
al. [15].

######  Theorem 2.2.

Let $r\geqslant 2$, $n\geqslant 1$, $G$ be a simple edge-coloured graph with
$n$ vertices and $n$ colours, where each colour class has size at least
$301r\log r$. Then $G$ contains a rainbow cycle of length at most
$\lceil\frac{n}{r}\rceil$.

Theorem 2.2 was subsequently improved by Hompe and Spirkl [17], who removed
the $\log r$ term.

######  Theorem 2.3.

Let $r,n\in\mathbb{N}$, $G$ be a simple edge-coloured graph with $n$ vertices
and $n$ colours, where each colour class has size at least $10^{11}r$. Then
$G$ contains a rainbow cycle of length at most $\frac{n}{r}$.

###  2.2. Number of Colour Classes

One appealing aspect of Aharoni’s conjecture is that we can ask what happens
when the number of colour classes is different from the number of vertices.
Note that this question does not even make sense in the digraph setting. To be
precise, we now define a function $f(n,t,r)$ which will be useful to state
many of the results that appear in this survey. The _rainbow girth_ of an
edge-coloured graph $G$, denoted $\operatorname{rg}(G)$, is the length of a
shortest rainbow cycle in $G$. If $G$ does not contain a rainbow cycle, then
$\operatorname{rg}(G)=\infty$. Let

$f(n,t,r)\coloneqq\max\\{\operatorname{rg}(G)\\},$

where the maximum is taken over all simple edge-coloured graphs $G$ with $n$
vertices and at least $t$ colours, such that each colour class has size at
least $r$.

We can rephrase Aharoni’s conjecture via our function $f(n,t,r)$ as follows.

######  Conjecture 2.4 (Aharoni).

For all $n,r\geqslant 1$,

$f(n,n,r)\leqslant\lceil\tfrac{n}{r}\rceil.$

We believe that there is no reason to restrict attention to the case $t=n$,
and that the following question is of independent interest.

######  Question 2.5.

Obtain good upper and lower bounds for $f(n,t,r)$ for all $n,t$, and $r$.

An important special case of Question 2.5 is when $r=1$, which was considered
by Bollobás and Szemerédi [7].

######  Theorem 2.6.

For all $n\geqslant 4$ and $k\geqslant 2$,

$f(n,n+k,1)\leqslant\frac{2(n+k)}{3k}(\log k+\log\log k+4).$

In other words, Theorem 2.6 asserts that every $n$-vertex graph with at least
$n+k$ edges contains a cycle of length at most $\frac{2(n+k)}{3k}(\log
k+\log\log k+4)$. This is a key tool used in many of the results presented in
this survey.

Hompe and Spirkl [17] also obtained the following bounds when the number of
colours is more than the number of vertices.

######  Theorem 2.7.

For all $n\geqslant 1$ and $k\geqslant 2$,

$f(n,n+k,10^{9}k)\leqslant\min\\{6,\frac{n(\log k)^{2}}{10k^{3/2}}+14\log
k\\}.$

When the number of colours is _less_ than the number of vertices, DeVos et al.
[9] obtained the following tight bounds for $r=2$.

######  Theorem 2.8.

For all $n\geqslant 3$ and $t\leqslant n$,

$f(n,t,2)=\begin{cases}\infty&\text{if $t\leqslant n-2$,}\\\ n-1&\text{if
$t=n-1$,}\\\ \lceil\frac{n}{2}\rceil&\text{if $t=n$}.\end{cases}$

###  2.3. Structured Colour Classes

In the proof of the Caccetta-Häggkvist conjecture (assuming Aharoni’s
conjecture) given in the Introduction, the colour classes of the derived edge-
colouring are all stars. Therefore, it is natural to ask what happens when the
colour classes are not stars. Note that if a colour class is not a star, then
it must contain a matching of size 2, or it is a triangle.

In the extreme case when all colour classes contain a matching of size 2,
Aharoni and Guo [5] proved that there is a much shorter rainbow cycle than the
$\lceil\frac{n}{2}\rceil$ bound which follows from [9].

######  Theorem 2.9.

There exists an absolute constant $C$ such that if $G$ is a simple edge-
coloured graph with $n$ vertices, $n$ colours, and each colour class is a
matching of size 2, then $G$ contains a rainbow cycle of length at most $C\log
n$.

Kevin Hendrey (private communication) proved that a $\mathcal{O}(\log n)$
bound also holds in the case when all colour classes are a triangle. The same
proof also appears in a recent paper of Aharoni et al. [1].

######  Theorem 2.10.

There exists an absolute constant $C$ such that if $G$ is a simple edge-
coloured graph with $n$ vertices, $n$ colours, and each colour class is a
triangle, then $G$ contains a rainbow cycle of length at most $C\log n$.

Some mixed cases were investigated by Guo [10].

######  Theorem 2.11.

There exists an absolute constant $C$ such that if $G$ is a simple edge-
coloured graph with $n$ vertices, $n$ colours, and each colour class is a
matching of size 2 or a triangle, then $G$ contains a rainbow cycle of length
at most $C\log n$.

######  Theorem 2.12.

For any constants $0\leqslant\alpha<1$ and $0\leqslant\beta\leqslant\alpha$
with $\beta<(1-\alpha)/3$, there exists a constant $C(\alpha,\beta)$ such that
if $G$ is an $n$-vertex simple edge-coloured graph containing at least
$(\alpha-\beta)n$ color classes consisting of a single edge and at least
$(1-\alpha-\beta)n$ color classes consisting of a triangle, then $G$ contains
a rainbow cycle of length at most $C(\alpha,\beta)\log n$.

###  2.4. Rainbow Triangles

The rainbow triangle case ($r=\lceil n/3\rceil$) of Aharoni’s conjecture
states that $f(n,n,\lceil n/3\rceil)\leqslant 3$. This is of course still open
since the directed triangle case of the Caccetta-Häggkvist conjecture is still
open. However, there have been partial results which increase the number of
colours or sizes of the colour classes. Two such results were obtained by
Aharoni et al. [4].

######  Theorem 2.13.

For all $n\geqslant 1$,

$f(n,9n/8,n/3)\leqslant 3.$

######  Theorem 2.14.

For all $n\geqslant 1$,

$f(n,n,2n/5)\leqslant 3.$

Both of these results have been subsequently improved by Hompe et al. [16].

######  Theorem 2.15.

For all $n\geqslant 1$,

$f(n,1.1077n,n/3)\leqslant 3.$

######  Theorem 2.16.

For all $n\geqslant 1$,

$f(n,n,0.3988n)\leqslant 3.$

Aharoni et al. [3] proved the following theorem showing when a simple edge-
coloured graph with 3 colours contains a rainbow triangle. Their theorem
actually implies Mantel’s theorem.

######  Theorem 2.17.

Every $n$-vertex simple edge-coloured graph with 3 colours and each colour
class of size at least $\frac{26-2\sqrt{7}}{81}\cdot n^{2}$ contains a rainbow
triangle.

They also prove that the constant $\frac{26-2\sqrt{7}}{81}$ in Theorem 2.17 is
best possible. However, their extremal example has rainbow 2-cycles. Our first
new result is the following sharp thresholds for $f(n,3,r)$.

######  Theorem 2.18.

For all $n\geqslant 100$,

$f(n,3,r)=\begin{cases}\infty&\text{if
$r\leqslant\lfloor\binom{n}{2}/3\rfloor$,}\\\ 2&\text{if
$\lfloor\binom{n}{2}/3\rfloor<r\leqslant\binom{n}{2}$,}\\\ 1&\text{if
$r>\binom{n}{2}$.}\end{cases}$

###### Proof.

First suppose $r>\lfloor\binom{n}{2}/3\rfloor$. Let $G$ be a simple edge-
coloured graph with $n$ vertices, 3 colours and each colour class of size at
least $r$. Since $K_{n}$ has only $\binom{n}{2}$ edges, $G$ must contain a
loop or a rainbow 2-cycle. Moreover, if $r>\binom{n}{2}$, then $G$ must
contain a loop. The $n$-vertex edge-coloured graph with a red, blue, and green
edge between every pair of vertices proves equality.

We now show that $f(n,3,r)=\infty$ if $n\geqslant 100$ and
$r\leqslant\lfloor\binom{n}{2}/3\rfloor$. Partition the vertices of $K_{n}$ as
$X\cup Y\cup Z$ where $|X|=|Y|=\lceil\frac{2n}{5}\rceil$. Colour all edges in
$K_{n}[X]$ or $K_{n}[Y]$ or $K_{n}[Z]$ red, all edges between $X$ and $Y$
blue, and all edges between $Z$ and $X\cup Y$ green. Observe that this is an
edge-colouring of $K_{n}$ with no rainbow triangle. The colour classes do not
quite have the same size, which we now fix. Since $n\geqslant 100$, we have
$|X||Y|\leqslant\binom{n}{2}/3$ and $|Z|(|X|+|Y|)\leqslant\binom{n}{2}/3$.
Thus, we may recolour some of the edges in $K_{n}[X]$ blue, and some of the
edges in $K_{n}[Y]$ green, so that the number of red, blue, and green edges
differ by at most 1. This new edge-colouring of $K_{n}$ still does not contain
a rainbow triangle. This of course implies that there are no rainbow cycles
since there are only 3 colours. ∎

###  2.5. Small Values of $r$

The Caccetta-Häggkvist conjecture is known to hold for small values of $r$.
The $r=1$ case is trivial, the $r=2$ case was proven by Caccetta and Häggkvist
[8]; the $r=3$ case was proven by Hamidoune [11]; and the $r\in\\{4,5\\}$
cases were proven by Hoàng and Reed [13]. For Aharoni’s conjecture, the $r=2$
case was proven by DeVos et al. [9].

######  Theorem 2.19.

For all $n\geqslant 1$,

$f(n,n,2)\leqslant\lceil\tfrac{n}{2}\rceil.$

In Section 3, we will prove the following result for $r=3$.

######  Theorem 2.20.

For all $n\geqslant 1$,

$f(n,n,3)\leqslant\tfrac{4n}{9}+7.$

###  2.6. Non-uniform Versions

For the Caccetta-Häggkvist conjecture, it is natural to ask if there is a
version which takes into account _all_ the outdegrees rather than just the
minimum outdegree. Seymour (see [14]) proposed the following generalization.
Given a digraph $D$ with no sink444A _sink_ is a vertex with outdegree zero.,
define

$\psi(D):=\sum_{v\in V(D)}\frac{1}{\deg^{+}(v)}.$

######  Conjecture 2.21.

Every simple digraph $D$ with no sink contains a directed cycle of length at
most $\lceil\psi(D)\rceil$.

Note that in the case that all outdegrees are $r$, then $\psi(D)=\frac{n}{r}$,
so Conjecture 2.21 implies the Caccetta-Häggkvist conjecture. Unfortunately,
Conjecture 2.21 was disproved by Hompe [14]. However, Aharoni et al. [1]
proved that "half" of Conjecture 2.21 holds.

######  Theorem 2.22.

Every simple digraph $D$ with no sink contains a directed cycle of length at
most $2\psi(D)$.

Theorem 2.22 has a natural generalization in the rainbow setting. Given an
edge-coloured graph $G$, define

$\psi(G)=\sum_{A}\frac{1}{|A|},$

where the sum is taken over all colour classes $A$ of $G$.

######  Conjecture 2.23.

Every simple edge-coloured graph $G$ with the same number of colours as
vertices contains a rainbow cycle of length at most $2\psi(G)$.

In the case that all colour classes have size at most 2, Aharoni et al. [1]
proved the following strengthening of Conjecture 2.23.

######  Theorem 2.24.

Let $G$ be a simple edge-coloured graph with the same number of colours as
vertices and such that each colour class has size at most 2. Then $G$ contains
a rainbow cycle of length at most $\lceil\psi(G)\rceil$.

Note that Theorem 2.24 is a strengthening of Theorem 2.19 since it allows
colour classes of size 1.

###  2.7. Matroids

We can generalise Aharoni’s conjecture to any setting in which the notion of
‘cycle’ makes sense. One natural candidate is that of a _matroid_. For the
reader unfamiliar with matroids, we introduce all the necessary definitions
now. For a more thorough introduction to matroids, we refer the reader to
Oxley [18].

A _matroid_ is a pair $M=(E,\mathcal{C})$ where $E$ is a finite set, called
the _ground set_ of $M$, and $\mathcal{C}$ is a collection of subsets of $E$,
called _circuits_ , satisfying

  1. (1)

$\emptyset\notin\mathcal{C}$,

  2. (2)

if $C^{\prime}$ is a proper subset of $C\in\mathcal{C}$, then
$C^{\prime}\notin\mathcal{C}$,

  3. (3)

if $C_{1}$ and $C_{2}$ are distinct members of $\mathcal{C}$ and $e\in
C_{1}\cap C_{2}$, then there exists $C_{3}\subseteq(C_{1}\cup
C_{2})\setminus\\{e\\}$.

We now give some examples of matroids. Let $G$ be a graph. We will consider
two different matroids with ground set $E(G)$. The circuits of the first
matroid are the (edges of) cycles of $G$. This is the _cycle matroid_ of $G$,
denoted $M(G)$. A matroid is _graphic_ if it is isomorphic to the cycle
matroid of some graph. A _cocycle_ of $G$ is an inclusion-wise minimal edge-
cut of $G$. The collection of cocycles of $G$ is also a matroid, called the
_cocycle matroid_ of $G$, and is denoted $M(G)^{*}$. A matroid is _cographic_
if it is isomorphic to the cocycle matroid of some graph.

Let $\mathbb{F}$ be a field. An _$\mathbb{F}$ -matrix_ is a matrix with
entries in $\mathbb{F}$. Let $A$ be an $\mathbb{F}$-matrix whose columns are
labelled by a finite set $E$. The _column matroid_ of $A$, denoted $M[A]$, is
the matroid with ground set $E$ whose circuits correspond to the minimal
(under inclusion) linearly dependent columns of $A$. A matroid is
_representable over $\mathbb{F}$_ if it is isomorphic to $M[A]$ for some
$\mathbb{F}$-matrix $A$. A matroid is _binary_ if it is representable over the
two-element field, and it is _regular_ if it is representable over every
field.

In order to formulate Aharoni’s conjecture for matroids, we need to define
simple matroids and how to express the number of vertices of a graph as a
matroid parameter. We do this now. A matroid is _simple_ it it does not
contain any circuits of size $1$ or $2$. A set $I\subseteq E$ is _independent_
if it does not contain a circuit. The _rank_ of $X\subseteq E$ is the size of
a largest independent set contained in $X$, and is denoted $r_{M}(X)$. The
_rank_ of $M$ is $r(M)\coloneqq r_{M}(E)$. Notice that the number of vertices
of a connected graph $G$ is $r(M(G))-1$. Thus, Aharoni’s conjecture can be
phrased in the language of matroids as follows.

######  Conjecture 2.25 (Aharoni).

Let $M$ be a simple rank-$(n-1)$ graphic matroid and $c$ be a colouring of
$E(M)$ with $n$ colours, where each colour class has size at least $r$. Then
$M$ contains a rainbow circuit of size at most $\lceil\frac{n}{r}\rceil$.

One way to generalise Conjecture 1.1 is to replace ‘graphic matroid’ with some
larger superclass of matroids. In [9], it was shown that one cannot replace
‘graphic matroid’ by ‘binary matroid’ in Conjecture 2.25.

######  Theorem 2.26.

For all $n\geqslant 6$, there exists a simple rank-$(n-1)$ binary matroid $M$
on $2n$ elements, and a colouring of $E(M)$ where each colour class has size
$2$, such that all rainbow circuits of $M$ have size strictly greater than
$\lceil\frac{n}{2}\rceil$.

The main result of [9] can be phrased in matroid language as follows.

######  Theorem 2.27.

Let $M$ be a simple rank-$(n-1)$ graphic matroid and $c$ be a colouring of
$E(M)$ with $n$ colours, where each colour class has size at least $2$. Then
$M$ contains a rainbow circuit of size at most $\lceil\frac{n}{2}\rceil$.

In [9], it is also proved that the matroid analogue of Theorem 2.19 holds for
cographic matroids.

######  Theorem 2.28.

Let $N$ be a simple rank-$(n-1)$ cographic matroid and $c$ be a colouring of
$E(N)$ with $n$ colours, where each colour class has size at least $2$. Then
$N$ contains a rainbow circuit of size at most $\lceil\frac{n}{2}\rceil$.

Regular matroids are a well-studied superclass of graphic matroids, and are
‘essentially’ graphic or cographic via Seymour’s regular matroid decomposition
theorem [20]. Therefore, by combining Theorem 2.27, Theorem 2.28, and
Seymour’s regular matroid decomposition theorem, it may be possible to prove
the following conjecture.

######  Conjecture 2.29 (DeVos et al. [9]).

Let $M$ be a simple rank-$(n-1)$ regular matroid and $c$ be a colouring of
$E(M)$ with $n$ colours, where each colour class has size at least $2$. Then
$M$ contains a rainbow circuit of size at most $\lceil\frac{n}{2}\rceil$.

Of course, we can also consider Question 2.5 for various classes of matroids.
Bérczi and Schwarcz [6] obtained one such result.

######  Theorem 2.30.

Let $M$ be an $n$-element rank-$t$ binary matroid whose ground set is coloured
with $t$ colours. Then $M$ either contains a rainbow circuit or a
monochromatic cocircuit.555A _monochromatic cocircuit_ is a circuit in the
dual matroid whose elements are all the same colour.

Bérczi and Schwarcz [6, Theorem 4] also show that it is possible to
characterize binary matroids as exactly those matroids which do not admit a
specific type of colouring with no rainbow circuits. They also prove that if a
simple graph $G$ has an edge-colouring with no rainbow cycle, where each
colour class has size at most 2, then $G$ is independent in the 2-dimensional
rigidity matroid.666Equivalently, for every $X\subseteq V(G)$ with
$|X|\geqslant 2$, $|E(G[X])|\leqslant 2|X|-3$.

##  3\. Proof of Main Theorem

In this section, we prove our main theorem.

######  Theorem 3.1.

Every simple edge-coloured graph with $n$ vertices, $n$ colours, and each
colour class of size at least 3, contains a rainbow cycle of length at most
$\tfrac{4n}{9}+7$.

###  3.1. Excess-$k$ Graphs

We begin by establishing some basic properties about graphs which have at
least $k$ more edges than vertices, which we call _excess- $k$ graphs_. The
first property follows from Theorem 2.6: for all $n\geqslant 4$ and
$k\geqslant 2$, every $n$-vertex, excess-$k$ graph has a cycle of length at
most $\frac{2(n+k)}{3k}(\log k+\log\log k+4)$. We require the following
tighter bounds when $k\leqslant 2$.

######  Lemma 3.2.

Every $n$-vertex, excess-1 graph has a cycle of length at most
$\frac{2n}{3}+1$.

The proof is easy and is omitted (see [9] for a proof of a stronger claim).

######  Lemma 3.3.

Every $n$-vertex, excess-2 graph $H$ has a cycle of length at most
$\frac{n}{2}+1$.

###### Proof.

A _block_ of $H$ is a 2-connected subgraph of $H$ which is maximal under the
subgraph relation. If $H$ contains at least two blocks, then $H$ contains two
cycles which meet in at most one vertex. Hence, one of these cycles has length
at most $\frac{n}{2}+1$. So, we may assume $H$ contains exactly one block $B$.
Note that $B$ is excess-2, since $H$ is excess-2. Let $C\cup
P_{1}\cup\dots\cup P_{k}$ be an ear-decomposition of $B$. Note that
$k\geqslant 2$, since $B$ is excess-2. Let $B^{\prime}=C\cup P_{1}\cup P_{2}$.
Either $B^{\prime}$ contains two cycles which meet in at most two vertices, or
$B^{\prime}$ is a subdivision of $K_{4}$. In the first case, one of the two
cycles has length at most $\frac{n}{2}+1$. In the second case, $B^{\prime}$
contains four cycles $C_{1},\dots,C_{4}$ such that
$\sum_{i\in[4]}|V(C_{i})|=2|V(B^{\prime})|+4$. Thus, one of these four cycles
has length at most $\frac{|V(B^{\prime})|}{2}+1\leqslant\frac{n}{2}+1$. ∎

We now prove that the largest stable set of an excess-$k$ graph is roughly
half the number of vertices.

######  Lemma 3.4.

Let $H$ be a simple excess-$k$ graph of minimum degree at least 2. Then a
maximum stable set of $H$ has size at most $\frac{|V(H)|+k}{2}$.

###### Proof.

We proceed by induction on $|V(H)|+|E(H)|$. We may assume that $H$ has exactly
$k$ more edges than vertices. If $H$ is the disjoint union of
$H_{1},\dots,H_{\ell}$ and $H_{i}$ has excess $k_{i}$, then
$k_{1}+\dots+k_{\ell}=k$. Therefore, we are done by applying induction to each
$H_{i}$. So, we may assume $H$ is connected. If $k=0$, then $H$ is a cycle, so
the lemma clearly holds. Now suppose $k\geqslant 1$. Let $X$ denote the set of
vertices of $H$ of degree at least 3. If $|X|=1$, then $H$ consists of $k+1$
cycles which meet at the same vertex. It is easy to see that the lemma holds
in this case. So, we may assume $|X|\geqslant 2$. Suppose $u,v\in X$ and
$uv\in E(G)$. By induction, a maximum stable set of $H-uv$ has size at most
$\frac{|V(H)|+k-1}{2}$. Hence, a maximum stable set of $H$ has size at most
$\frac{|V(H)|+k-1}{2}$. So, we may assume that no two vertices of $X$ are
adjacent.

Let $P$ be the shortest path between any two vertices of $X$. By the
minimality of $P$, each internal vertex of $P$ has degree 2. Let
$H^{\prime}=H-I$, where $I$ is the set of internal vertices of $P$. Note that
$H$’ has excess $k-1$ and minimum degree at least 2. Let $S$ be a maximum size
stable set in $H$. Note that $S\cap V(H^{\prime})$ is a stable set in
$H^{\prime}$. By induction, $|S\cap
V(H^{\prime})|\leqslant(|V(H^{\prime})|+k-1)/2$. Also, $|S\cap
I|\leqslant(|I|+1)/2$. Thus, $|S|=|S\cap V(H^{\prime})|+|S\cap
I|\leqslant(|V(H)|+k)/2$. ∎

We finish by establishing the following lemma about ‘minimal’ excess-$k$
rainbow subgraphs of an edge-coloured graph.

######  Lemma 3.5.

Let $H$ be a simple edge-coloured graph where each colour class has size at
most $r$. Let $R$ be an excess-$k$ rainbow subgraph of $H$ such that $V(R)$ is
minimal under inclusion. Then $H$ contains a rainbow 2-cycle, or there are at
most $\max\\{\binom{2k+2}{2},6k(r-1)\\}$ chords of $R$ in $H$.

###### Proof.

We may assume that $H$ does not contain parallel edges; otherwise $H$ contains
a rainbow 2-cycle. By the minimality of $R$, $\deg_{R}(v)\geqslant 2$ for all
$v\in V(R)$. Let $V(R)=X\cup Y$, where $X$ is the set of vertices of degree at
least 3, and $Y$ is the set of degree-2 vertices of $R$. By the Handshaking
Lemma, $|X|\leqslant 2k$.

Say that a chord of $R$ is _novel_ if its colour does not appear in $R$, and
_plain_ otherwise. Suppose $e=uv$ is a novel chord. If $|Y|\geqslant 3$, then
there is a vertex $y\in Y$ such $y\notin\\{u,v\\}$, and so $(R\cup e)-y$
contradicts the minimality of $R$. Thus, there are either no novel chords, or
the total number of chords is at most
$\binom{|X|+|Y|}{2}\leqslant\binom{2k+2}{2}$.

We may thus assume that there are no novel chords. Let $e\in E(H)$ be a plain
chord of $R$. Since $e$ is plain, there is an edge $f\in E(R)$ of the same
colour as colour $e$. If both ends of $f$ are in $Y$, then
$R^{\prime}\coloneqq(R\cup e)\setminus f$ contains a degree-1 vertex $x$. But
now $R^{\prime}-x$ contradicts the minimality of $R$. Therefore, at least one
end of $f$ is in $X$. Let $R_{0}$ be the multigraph on vertex set $X$ obtained
by suppressing all degree-2 vertices. Note that $R_{0}$ also has excess $k$
and at most $2k$ vertices. Therefore, $|E(R_{0})|\leqslant 3k$. There are at
most $2|E(R_{0})|$ edges of $R$ which are incident to a vertex in $X$. Each of
these edges can correspond to at most $r-1$ plain chords. Hence, there are at
most $6k(r-1)$ plain chords. ∎

###  3.2. The set-up

Let $G$ be a simple edge-coloured graph with $n$ vertices, $n$ colours, and
each colour class of size exactly 3. An _$r$ -star_ is a star with $r$ edges.
A colour class of $G$ is a _star class_ if it is a 3-star. A vertex of $G$ is
a _star vertex_ if it is the centre of a star class, and is otherwise a _non-
star vertex_. Let $S$ denote the set of star vertices of $G$, and $N$ denote
the set of non-star vertices of $G$. Let $N^{\prime}$ be the set of non-star
classes. Since star classes may be centred at the same vertex, we have
$|N^{\prime}|\leqslant|N|$. We will do a case analysis depending on whether
$|N|\geqslant 8$ or $|N|\leqslant 7$.

###  3.3. Many non-star vertices

Throughout this section we suppose $|N|\geqslant 8$. Let $\\{x,y\\}\subseteq
N$. We say that a colour class $A$ _dominates_ $\\{x,y\\}$ if every edge in
$A$ has an end in $\\{x,y\\}$.

######  Claim 3.6.

There exists $\\{x,y\\}\subseteq N$ such that no colour class dominates
$\\{x,y\\}$.

###### Proof.

Suppose $A$ is a star class. Then $A$ is a 3-star centred at a vertex not in
$N$. Therefore, for all $\\{u,v\\}\subseteq N$, $A$ does not dominate
$\\{u,v\\}$ since at least one leaf of $A$ is not in $\\{u,v\\}$.

Suppose $A$ is a non-star class. Up to isomorphism,
$A\in\\{K_{3},P_{3},P_{2}\sqcup P_{1},P_{1}\sqcup P_{1}\sqcup P_{1}\\}$, where
$P_{i}$ is a path with $i$ edges, and $\sqcup$ denotes disjoint union. Let
$\gamma(A)$ be the number of vertex covers of $A$ of size 2. Observe that the
number of pairs $\\{u,v\\}\subseteq N$ which $A$ dominates is exactly equal to
$\gamma(A)$. We have $\gamma(K_{3})=3,\gamma(P_{3})=1,\gamma(P_{2}\sqcup
P_{1})=2$, and $\gamma(P_{1}\sqcup P_{1}\sqcup P_{1})=0$. Thus, every non-star
class dominates at most 3 pairs of vertices in $N$. So, the number of pairs
dominated by non-star classes is at most $3|N^{\prime}|\leqslant
3|N|<\binom{N}{2}$, since $|N|\geqslant 8$. Therefore, at least one pair
$\\{x,y\\}\subseteq N$ is not dominated by any colour class. ∎

######  Claim 3.7.

$G$ contains an excess-2 rainbow subgraph $R$.

###### Proof.

A _transversal_ of $G$ is a subgraph consisting of exactly one edge of each
colour. By Claim 3.6, $G$ has a transversal $R$ such that at least two
vertices $x,y$ are not in $V(R)$. Since $R$ has exactly $n$ edges, $R$ is
excess-2 (and clearly rainbow). ∎

We now choose $R$ to be an excess-2 rainbow subgraph of $G$ such that $V(R)$
is minimal under inclusion.

######  Claim 3.8.

$G$ contains a rainbow cycle $C^{\prime}$ such that $E(R)\cap
E(C^{\prime})=\emptyset$.

###### Proof.

Choose a transversal $R^{\prime}$ which is edge-disjoint from $R$. Since
$R^{\prime}$ has $n$ vertices and $n$ edges, $R^{\prime}$ contains a cycle
$C^{\prime}$. Clearly, $C^{\prime}$ is rainbow since $R^{\prime}$ is rainbow.
∎

######  Claim 3.9.

$G$ contains a rainbow cycle $C$ of length at most $\frac{2n}{5}+7$.

###### Proof.

Let $n_{1}=|V(R)\setminus V(C^{\prime})|$, $n_{2}=|V(R)\cap V(C^{\prime})|$,
and $n_{3}=|V(C^{\prime})\setminus V(R)|$. First suppose
$n_{3}\geqslant\frac{n}{5}-12$. Then, $|V(R)|\leqslant\frac{4n}{5}+12$. By
Lemma 3.3, $R$ contains a rainbow cycle of length at most
$\frac{1}{2}\cdot(\frac{4n}{5}+12)+1=\frac{2n}{5}+7$.

Thus, we may assume that $n_{3}<\frac{n}{5}-12$. Let $A$ be the subset of
edges of $C^{\prime}$ which are chords of $R$. Applying Lemma 3.5 to $R$ in
$C^{\prime}\cup R$ (so $r=2$), we have $|A|\leqslant 15$. Note that $V(R)\cap
V(C^{\prime})$ is a stable set of $C^{\prime}\setminus A$. The maximum stable
set of $C^{\prime}$ has size at most $\frac{|V(C^{\prime})|}{2}$. Deleting one
edge from a graph can increase the size of a maximum stable set by at most 1.
Therefore, we conclude that $n_{2}\leqslant n_{3}+2|A|\leqslant n_{3}+30$.
Thus,

$|V(C^{\prime})|=n_{2}+n_{3}\leqslant
2n_{3}+30<2(\tfrac{n}{5}-12)+30=\tfrac{2n}{5}+6,$

and so we may take $C=C^{\prime}$ in this case. ∎

This completes the case $\lvert N\rvert\geqslant 8$, since we have found a
rainbow cycle of length at most $\frac{2n}{5}+7$, which is better than the
bound of $\frac{4n}{9}+7$ required by Theorem 3.1.

###  3.4. Few non-star vertices

We complete the proof by considering the case $\lvert N\rvert\leqslant 7$.

######  Claim 3.10.

At least one vertex of $G$ is a non-star vertex.

###### Proof.

Suppose every vertex of $G$ is a star vertex. Since $G$ has the same number of
vertices as colours, this implies that at each $v\in V(G)$ there is a star
class $S_{v}$ centred at $v$. Let $D$ be the digraph obtained from $G$ by
orienting the edges of $S_{v}$ away from $v$ for all $v\in V(G)$. By the $r=3$
case of the Caccetta-Häggkvist conjecture [11], $D$ contains a directed cycle
$\vec{C}$ of length at most $\lceil\frac{n}{3}\rceil$. Note that $\vec{C}$
corresponds to a rainbow cycle $C$ in $G$. ∎

Fix a non-star vertex $z\in V(G)$. Since $z$ is a non-star vertex, for every
colour $a$, there is an edge $e_{a}$ coloured $a$ such that $e_{a}$ is not
incident to $z$. Thus, there is a transversal $R$ of $G$ such that $z\notin
V(R)$. In particular, $R$ is an excess-1 rainbow subgraph of $G$ such that
$z\notin V(R)$. Let $R_{1}$ be an excess-1 rainbow subgraph of $G-z$ such that
$V(R_{1})$ is minimal under inclusion.

######  Claim 3.11.

There exists a transversal $R_{2}^{\prime}$ of $G$ such that $z\notin
V(R_{2}^{\prime})$ and $|E(R_{1})\cap E(R_{2}^{\prime})|\leqslant 7$.

###### Proof.

Let $A$ be a star colour class. Observe that there are at least 2 edges of $A$
which are not incident to $z$. Thus, there exists an edge $e_{A}\in A$ such
that $e_{A}\notin E(R_{1})$ and $e_{A}$ is not incident to $z$. If $A$ is a
non-star colour class, there is an edge $e_{A}\in A$ which is not incident to
$z$. Let $R_{2}^{\prime}=\bigcup_{A}\\{e_{A}\\}$, where the union is over all
colour classes. Since there are at most $|N^{\prime}|\leqslant|N|\leqslant 7$
non-star colour classes, $|E(R_{1})\cap E(R_{2}^{\prime})|\leqslant 7$. ∎

Since $z\notin V(R_{2}^{\prime})$, $R_{2}^{\prime}$ is excess-1 (and rainbow).
Let $R_{2}\subseteq R_{2}^{\prime}$ be excess-1 and rainbow such that
$V(R_{2})$ is minimal under inclusion. In particular, $R_{2}$ has minimum
degree at least 2.

######  Claim 3.12.

$G$ contains a rainbow cycle $C$ of length at most $\frac{4n}{9}+7$.

###### Proof.

Let $n_{1}=|V(R_{1})\setminus V(R_{2})|$, $n_{2}=|V(R_{1})\cap V(R_{2})|$, and
$n_{3}=|V(R_{2})\setminus V(R_{1})|$. First suppose
$n_{3}\geqslant\frac{n}{3}-9$. Thus, $|V(R_{1})|\leqslant\frac{2n}{3}+9$. By
Lemma 3.2, $R_{1}$ contains a rainbow cycle of length at most
$\frac{2}{3}\cdot(\frac{2n}{3}+9)+1=\frac{4n}{9}+7$.

Thus, we may assume that $n_{3}<\frac{n}{3}-9$. Let $A$ be the subset of edges
of $R_{2}$ which are chords or edges of $R_{1}$. By Lemma 3.5 applied to
$R_{1}$ in $R_{1}\cup R_{2}$ (so $r=2$), and Claim 3.11, $|A|\leqslant
6+7=13$. Note that $V(R_{1})\cap V(R_{2})$ is a stable set of $R_{2}\setminus
A$. By Lemma 3.4, the maximum stable set of $R_{2}$ has size at most
$\frac{|V(R_{2})|+1}{2}$. Deleting one edge from a graph can increase the size
of a maximum stable set by at most 1. Therefore, we conclude that
$n_{2}\leqslant n_{3}+2|A|+1\leqslant n_{3}+27$. By Lemma 3.2, $R_{2}$
contains a rainbow cycle of length at most

$\tfrac{2}{3}\cdot(n_{2}+n_{3})+1\leqslant\tfrac{2}{3}\cdot(2n_{3}+27)+1<\tfrac{2}{3}\cdot(2(\tfrac{n}{3}-9)+27)+1=\tfrac{4n}{9}+7.\qed$

Claim 3.12 completes the proof of Theorem 3.1.

##  4\. Generalising our Approach

For the $r=3$ case of Aharoni’s conjecture, we proved that there is a rainbow
cycle of length at most $\frac{4n}{9}+7$. The additive constant can be easily
improved since there are stronger versions of Lemma 3.5 for $k\leqslant 2$.
However, we opted to prove Lemma 3.5 for all $r$ and $k$ in case anyone would
like to generalize our approach.

Our strategy was to handle the cases of many non-star vertices and few non-
star vertices separately. For $r=3$, ‘many’ meant at least 8, but for larger
$r$ it can be a constant depending on $r$. Recall, that in the many non-star
case, we actually proved a better bound of $\frac{2n}{5}+7$. Thus, if we can
improve the few non-star case, we would get a better theorem. One tempting
strategy for the few non-star case is to use the following ‘defect’ version of
the Caccetta-Häggkvist conjecture due to Shen [21].

Let $D$ be a digraph. For each $r\in\mathbb{N}$, we define the _defect_ of $D$
to be

$\mathsf{def}_{r}(D)\coloneqq\sum_{u\in U}(r-\deg^{+}(u)),$

where $U$ is the set of vertices of $D$ of outdegree at most $r$.

######  Theorem 4.1 ([21]).

Let $D$ be a simple $n$-vertex digraph with no sink, and let $g$ be the length
of a shortest directed cycle of $D$. If $g\geqslant 2r-1$, then $n\geqslant
r(g-1)+1-\mathsf{def}_{r}(D)$.

The idea is that if the edges of each star colour class are oriented away from
their centres, then we obtain a digraph with small defect. Unfortunately, the
non-star vertices are sinks of this digraph, so we cannot apply Theorem 4.1
directly. It may be possible to apply Theorem 4.1 in some auxiliary digraph,
but we could not see a way to do this. For example, the case that there is
exactly one non-star vertex corresponds to the following conjecture about
digraphs, which we do not know how to solve.

######  Conjecture 4.2.

Let $D$ be a simple $n$-vertex digraph where each vertex except one has
outdegree at least $r$. Let $\\{s_{1},t_{1}\\},\dots,\\{s_{r},t_{r}\\}$ be $r$
distinct pairs of vertices in $D$. Then $D$ either contains a directed cycle
of length at most $\lceil\frac{n}{r}\rceil$ or there exist $i\in[r]$, $z\in
V(D)$, a directed path $P$ from $s_{i}$ to $z$, and a directed path $Q$ from
$t_{i}$ to $z$ such that $|E(P)|+|E(Q)|+1\leqslant\lceil\frac{n}{r}\rceil$.

For the many non-star case, our method can produce almost edge-disjoint,
rainbow subgraphs $H_{1},\dots,H_{\ell}$, each of excess-$k$, where $\ell$ and
$k$ depend on the definition of ‘many’ and on $r$. We conjecture that
$H_{1}\cup\dots\cup H_{\ell}$ should contain a short rainbow cycle, but were
unable to find a proof. Our attempted strategy was to introduce a variable for
every ‘region’ of the Venn diagram corresponding to
$V(H_{1}),\dots,V(H_{\ell})$, and to write out a linear program with
constraints coming from Theorem 2.6, Lemma 3.4, and Lemma 3.5. Unfortunately,
it turns out that our LP has a large dual solution and so it cannot prove non-
trivial bounds. However, it may be possible to add additional constraints to
our LP to obtain good bounds for general $r$.

### Acknowledgements

This research was initiated at the Structural Graph Theory Downunder II
workshop at the Mathematical Research Institute MATRIX (March 2022). We thank
Ron Aharoni and Zach Hunter for carefully reading an earlier version of this
paper and making some very helpful suggestions.

## References

  * Aharoni et al. [2021] Ron Aharoni, Eli Berger, Maria Chudnovsky, He Guo, and Shira Zerbib.  Non-uniform degrees and rainbow versions of the Caccetta-Häggkvist conjecture.  2021, arXiv:2110.11183.
  * Aharoni and Briggs [2022] Ron Aharoni and Joseph Briggs.  Choice functions.  _Order_ , pp. 1–19, 2022.
  * Aharoni et al. [2020] Ron Aharoni, Matt DeVos, Sebastián González Hermosillo de la Maza, Amanda Montejano, and Robert Šámal.  A rainbow version of Mantel’s theorem.  _Adv. Comb._ , pp. Paper No. 2, 12, 2020.
  * Aharoni et al. [2019] Ron Aharoni, Matthew DeVos, and Ron Holzman.  Rainbow triangles and the Caccetta-Häggkvist conjecture.  _J. Graph Theory_ , 92(4):347–360, 2019.
  * Aharoni and Guo [2021] Ron Aharoni and He Guo.  Rainbow cycles for families of matchings.  2021, arXiv:2110.14332.
  * Bérczi and Schwarcz [2022] Kristóf Bérczi and Tamás Schwarcz.  Rainbow and monochromatic circuits and cocircuits in binary matroids.  _Discrete Math._ , 345(6):Paper No. 112830, 11, 2022.
  * Bollobás and Szemerédi [2002] Béla Bollobás and Endre Szemerédi.  Girth of sparse graphs.  _J. Graph Theory_ , 39(3):194–200, 2002.
  * Caccetta and Häggkvist [1978] Louis Caccetta and R. Häggkvist.  On minimal digraphs with given girth.  In _Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978)_ , Congress. Numer., XXI, pp. 181–187. Utilitas Math., Winnipeg, Man., 1978.
  * DeVos et al. [2021] Matt DeVos, Matthew Drescher, Daryl Funk, Sebastián González Hermosillo de la Maza, Krystal Guo, Tony Huynh, Bojan Mohar, and Amanda Montejano.  Short rainbow cycles in graphs and matroids.  _J. Graph Theory_ , 96(2):192–202, 2021.
  * Guo [2022] He Guo.  Rainbow cycles for matchings, single edges, and triangles.  2022, arXiv:2210.12243.
  * Hamidoune [1987] Yahya Ould Hamidoune.  A note on minimal directed graphs with given girth.  _J. Combin. Theory Ser. B_ , 43(3):343–348, 1987.
  * Hladký et al. [2017] Jan Hladký, Daniel Král’, and Sergey Norin.  Counting flags in triangle-free digraphs.  _Combinatorica_ , 37(1):49–76, 2017.
  * Hoàng and Reed [1987] C. T. Hoàng and B. Reed.  A note on short cycles in digraphs.  _Discrete Math._ , 66(1-2):103–107, 1987.
  * Hompe [2019] Patrick Hompe.  The girth of digraphs and concatenating bipartite graphs.  _Princeton University Undergraduate Senior Thesis_ , 2019.
  * Hompe et al. [2021] Patrick Hompe, Petra Pelikánová, Aneta Pokorná, and Sophie Spirkl.  On Aharoni’s rainbow generalization of the Caccetta-Häggkvist conjecture.  _Discrete Math._ , 344(5):Paper No. 112319, 4, 2021.
  * Hompe et al. [2022] Patrick Hompe, Zishen Qu, and Sophie Spirkl.  Improved bounds for the triangle case of Aharoni’s rainbow generalization of the Caccetta-Häggkvist conjecture.  2022, arXiv:2206.10733.
  * Hompe and Spirkl [2022] Patrick Hompe and Sophie Spirkl.  Further approximations for Aharoni’s rainbow generalization of the Caccetta-Häggkvist conjecture.  _Electron. J. Combin._ , 29(1):Paper No. 1.55, 13, 2022.
  * Oxley [2011] James Oxley.  Matroid theory, vol. 21 of _Oxford Graduate Texts in Mathematics_.  Oxford University Press, Oxford, 2nd edn., 2011.
  * Razborov [2013] Alexander A. Razborov.  What is$\ldots$a flag algebra? _Notices Amer. Math. Soc._ , 60(10):1324–1327, 2013.
  * Seymour [1980] P. D. Seymour.  Decomposition of regular matroids.  _J. Combin. Theory Ser. B_ , 28(3):305–359, 1980.
  * Shen [2000] Jian Shen.  On the girth of digraphs.  _Discrete Math._ , 211(1-3):167–181, 2000.
  * Sullivan [2006] Blair D. Sullivan.  A summary of problems and results related to the Caccetta-Häggkvist conjecture.  2006, arXiv:math/0605646.
  * Thomassen [1994] Carsten Thomassen.  Every planar graph is $5$-choosable.  _J. Combin. Theory Ser. B_ , 62(1):180–181, 1994.

## Index