Partitioning edge-colored hypergraphs into few monochromatic tight cycles
Bustamante, Sebastián; Corsten, Jan; Frankl, Nora; Pokrovskiy, Alexey; and Skokan, Jozef
(2020)
Partitioning edge-colored hypergraphs into few monochromatic tight cycles
SIAM Journal on Discrete Mathematics, 34 (2).
1460 – 1471.
ISSN 0895-4801
Confirming a conjecture of Gyárfás, we prove that, for all natural numbers k and r, the vertices of every r-edge-colored complete k-uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles. We further prove that, for all natural numbers p and r, the vertices of every r-edge-colored complete graph can be partitioned into a bounded number of pth powers of cycles, settling a problem of Elekes, Soukup, Soukup, and Szentmiklóssy [Discrete Math., 340 (2017), pp. 2053-2069]. In fact we prove a common generalization of both theorems which further extends these results to all host hypergraphs of bounded independence number.
| Item Type | Article |
|---|---|
| Keywords | vertex partitioning,hypergraphs,tight cycles,PhD Studentship,DMS-1500121 |
| Departments | Mathematics |
| DOI | 10.1137/19M1269786 |
| Date Deposited | 06 Apr 2020 16:48 |
| URI | https://researchonline.lse.ac.uk/id/eprint/104001 |
Explore Further
-
picture_as_pdf - sidma.pdf
-
subject - Accepted Version
Download this file
Share this file
Downloads
ORCID: https://orcid.org/0000-0003-3996-7676