Monochromatic Path and Cycle Partitions in Hypergraphs

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

Abstract


Here we address the problem to partition edge colored hypergraphs by monochromatic paths and cycles generalizing a well-known similar problem for graphs.

We show that $r$-colored $r$-uniform complete hypergraphs can be partitioned into monochromatic Berge-paths of distinct colors. Also, apart from $2k-5$ vertices, $2$-colored $k$-uniform hypergraphs can be partitioned into two monochromatic loose paths.

In general, we prove that in any $r$-coloring of a $k$-uniform hypergraph there is a partition of the vertex set into
monochromatic loose cycles such that their number depends only on $r$ and $k$.


Keywords


Ramsey theory, monochromatic paths and cycles, hypergraphs

Full Text: PDF