Toward a rainbow Corrádi--Hajnal Theorem \RNum{1}
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916990690525184 |
|---|---|
| author | Jinghua, Deng Jianfeng, Hou caiyun, Hu xizhi, Liu |
| author_facet | Jinghua, Deng Jianfeng, Hou caiyun, Hu xizhi, Liu |
| contents | 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,\, \tfrac{n}{3}\right]$ for the parameter $t$.
In this work, we establish this conjecture for the first interval, $t \in \left[1,\, \tfrac{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 \tfrac{n - 57}{15}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_04018 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Toward a rainbow Corrádi--Hajnal Theorem \RNum{1} Jinghua, Deng Jianfeng, Hou caiyun, Hu xizhi, Liu Combinatorics 05C35, 05C65, 05D05 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,\, \tfrac{n}{3}\right]$ for the parameter $t$. In this work, we establish this conjecture for the first interval, $t \in \left[1,\, \tfrac{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 \tfrac{n - 57}{15}$. |
| title | Toward a rainbow Corrádi--Hajnal Theorem \RNum{1} |
| topic | Combinatorics 05C35, 05C65, 05D05 |
| url | https://arxiv.org/abs/2510.04018 |