Partitioning edge-colored hypergraphs into few monochromatic tight cycles

Bustamante, S., Corsten, J., Frankl, N., Pokrovskiy, A. & Skokan, J.ORCID logo (2020). Partitioning edge-colored hypergraphs into few monochromatic tight cycles. SIAM Journal on Discrete Mathematics, 34(2), 1460 – 1471. https://doi.org/10.1137/19M1269786
Copy

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.

picture_as_pdf

picture_as_pdf
sidma.pdf
subject
Accepted Version

Download
picture_as_pdf

picture_as_pdf
Edge.pdf
subject
Published Version

Download

Export as

EndNote BibTeX Reference Manager Refer Atom Dublin Core JSON Multiline CSV
Export