# Partitioning $2$-edge-colored Ore-type graphs by monochromatic cycles

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
We would like to report recent developments on Ramsey-type problems connected to the cycle partition number.
We colour the edges of a graph $G$ by red and blue.
In this context, it is conventional to accept {\it empty graphs and
one-vertex graphs} as a cycle (of any colour) and also {\it any edge}
as a cycle (in its colour). With this convention, one can define the
{\em cycle partition number} of any coloured graph $G$ as the minimum
number of vertex disjoint monochromatic cycles needed to cover the
vertex set of $G$.
Lehel conjectured that in every 2-colouring of the edges of
$K_n$, there is a vertex disjoint red and blue cycle which span
$V(K_n)$.
First there were results for large $n$, and finally Bessy and Thomass\'e [3] gave a
proof for all $n$.
One might suspect that the cycle partition number remains the same for dense graphs.
Imposing large minimum degree is one natural condition.
In [1] we posed the following
\medskip
{\bf Conjecture 1.}
If $G$ is an $n$-vertex graph with $\delta(G)>3n/4$, then in any
$2$-edge-colouring of $G$, there are two vertex disjoint
monochromatic cycles of different colours that span $V(G)$.
\medskip
In [1] we proved that Conjecture 1. nearly holds in an asymptotic sense.
That is, for all $\eta>0$ there exists $n_0$ such that if $G$ is a $2$-edge-coloured graph on $n>n_0$ vertices, then
there is a vertex disjoint red cycle and blue cycle spanning at least $(1-\eta)n$ vertices.
This was improved by DeBiasio and Nelsen
[4] who proved the statement for large $n$ under the condition $\delta(G)>(3/4+o(1))n$.
Recently Letzter [5] proved Conjecture 1. for large $n$.
Generalising Conjecture 1. for graphs satisfying an
Ore-type condition, we posed the following in [2]
\medskip
{\bf Conjecture 2}
If $G$ is an $n$-vertex graph such that for any two non-adjacent
vertices $x$ and $y$ of $G$, we have $deg(x)+deg(y)> 3n/2$, then in
any $2$-edge-colouring of $G$, there are two vertex disjoint
monochromatic cycles of different colours, which together cover
$V(G)$.
\medskip
We were able to prove a statement slightly weaker than Conjecture~2.
\medskip
{\bf Theorem 3.}
For every $\eta > 0$, there is an $n_0(\eta)=n_0$ such that the
following holds. If $G$ is an $n$-vertex graph with $n\geq n_0$ such
that for any two non-adjacent vertices $x$ and $y$ of $G$, we have
$deg(x)+deg(y)\ge (\frac{3}{2}+\eta) n$, then every
$2$-edge-coloring of $G$ admits two vertex disjoint monochromatic
cycles of different colors covering at least $(1-\eta)n$ vertices of
$G$.
\vspace{5mm}
\noindent{\bf References:}
\begin{itemize}
\item[{[1]}]
J. Balogh, J. Bar\'at, D. Gerbner, A. Gy\'arf\'as, G.N. S\'ark\"ozy,
Partitioning $2$-edge-colored graphs by monochromatic paths and
cycles, Combinatorica 34 (2014), 507--526.
\item[{[2]}]
J. Bar\'at, G.N. S\'ark\"ozy. Partitioning $2$-edge-colored Ore-type
graphs by monochromatic cycles. To appear in the Journal of Graph
Theory.
\item[{[3]}] S. Bessy, S. Thomass\'e, Partitioning a graph into a
cycle and an anticycle, a proof of Lehel's conjecture, J. Combin. Theory Ser. B 100 (2010), 176--180.
\item[{[4]}] L. DeBiasio, L. Nelsen, Monochromatic cycle partitions of graphs with large minimum
degree, retrieved from arXiv:1409.1874.
\item[{[5]}]
S. Letzter, Monochromatic cycle partitions of $2$-coloured graphs with minimum degree $3n/4$,
retrieved from arXiv:1502.07736.
\end{itemize}