Toward a rainbow Corrádi--Hajnal Theorem \RNum{1}

Abstract

We study an anti-Ramsey extension of the classical Corrádi--Hajnal Theorem: how many colors are needed to color the complete graph on $n$ vertices in order to guarantee a rainbow copy of $t{K}_3$, that is, $t$ vertex-disjoint triangles. We provide a conjecture for large $n$, consisting of five classes of different extremal constructions, corresponding to five subintervals of $\left[1,\frac{n}{3}\right]$ for the parameter $t$. In this work, we establish this conjecture for the first interval, $t\in \left[1,\frac{2n-6}{9}\right]$. In particular, this improves upon a recent result of Lu--Luo--Ma~[arXiv:2506.07115] which established the case $t\le \frac{n-57}{15}$.

arXiv comment28 pages, 8 figures