Minimum degree conditions for monochromatic cycle partitioning
| Autor: | Shoham Letzter, Richard Lang, Alexey Pokrovskiy, Dániel Korándi |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
010102 general mathematics
Ramsey theory Complete graph 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Partition (number theory) Combinatorics (math.CO) Monochromatic color 0101 mathematics Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series B. 146:96-123 |
| ISSN: | 0095-8956 |
| DOI: | 10.1016/j.jctb.2020.07.005 |
| Popis: | A classical result of Erd\H{o}s, Gy\'arf\'as and Pyber states that any $r$-edge-coloured complete graph has a partition into $O(r^2 \log r)$ monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant $c$ such that any $r$-edge-coloured graph on $n$ vertices with minimum degree at least $n/2 + c \cdot r \log n$ has a partition into $O(r^2)$ monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight. Comment: 22 pages (26 including appendix) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect