Rainbow even cycles
| Autor: | Dong, Zichao, Xu, Zijian |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics, vol. 38(2), 2024 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1137/23M1564808 |
| Popis: | We prove that every family of (not necessarily distinct) even cycles $D_1, \dotsc, D_{\lfloor 1.2(n-1) \rfloor+1}$ on some fixed $n$-vertex set has a rainbow even cycle (that is, a set of edges from distinct $D_i$'s, forming an even cycle). This resolves an open problem of Aharoni, Briggs, Holzman and Jiang. Moreover, the result is best possible for every positive integer $n$. Comment: 20 pages, 10 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|