UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Partitioning Edge-Colored Hypergraphs into Few Monochromatic Tight Cycles

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. Green open access

[img]
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 > 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
Downloads since deposit
9Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item