Partitioning edge-colored hypergraphs into few monochromatic tight cycles

Bustamante, Sebastián; Corsten, Jan; Frankl, Nora; Pokrovskiy, Alexey; and Skokan, JozefORCID logo (2020) Partitioning edge-colored hypergraphs into few monochromatic tight cycles SIAM Journal on Discrete Mathematics, 34 (2). 1460 – 1471. ISSN 0895-4801
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

Published Version


Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads