Monochromatic Loose-Cycle Partitions in Hypergraphs

András Gyárfás, Gábor Sárközy

Abstract


In this paper we study the monochromatic loose-cycle partition problem for non-complete hypergraphs. Our main result is that in any $r$-coloring of a $k$-uniform hypergraph with independence number $\alpha$ there is a partition of the vertex set into monochromatic loose cycles such that their number depends only on $r$, $k$ and $\alpha$. We also give an extension of the following result of Pósa to hypergraphs: the vertex set of every graph $G$ can be partitioned into at most $\alpha(G)$ cycles, edges and vertices.

Keywords


hypergraphs, monochromatic partitions, loose cycles

Full Text: PDF