Bustamante, S;
Corsten, J;
Frankl, N;
Pokrovskiy, A;
Skokan, J;
(2020)
Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles.
SIAM Journal on Discrete Mathematics
, 34
(2)
pp. 1460-1471.
10.1137/19M1269786.
Preview |
Text
Pokrovskiy_19m1269786.pdf - Published Version Download (709kB) | Preview |
Abstract
Confirming a conjecture of Gy´arf´as, 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´ossy [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.
| Type: | Article |
|---|---|
| Title: | Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/19M1269786 |
| Publisher version: | https://doi.org/10.1137/19M1269786 |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | vertex partitioning, hypergraphs, tight cycles |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112641 |
Archive Staff Only
 |
View Item |
