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

J\'anos Bar\'at
MTA-ELTE GAC

G\'abor S\'ark\"ozy
Alfr\'ed R\'enyi Institute of Mathematics

PDF

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}

Back to all abstracts