Decompositions of edge-colored infinite complete graphs into monochromatic paths

Abstract

An $r$-edge coloring of a graph or hypergraph $G=(V,E)$ is a map $c:E\to \{0,\dots ,r-1\}$. Extending results of Rado and answering questions of Rado, Gyárfás and Sárközy we prove that (1.) the vertex set of every $r$-edge colored countably infinite complete $k$-uniform hypergraph can be partitioned into $r$ monochromatic tight paths with distinct colors (a tight path in a $k$-uniform hypergraph is a sequence of distinct vertices such that every set of $k$ consecutive vertices forms an edge), (2.) for all natural numbers $r$ and $k$ there is a natural number $M$ such that the vertex set of every $r$-edge colored countably infinite complete graph can be partitioned into $M$ monochromatic $k^{th}$ powers of paths apart from a finite set (a $k^{th}$ power of a path is a sequence $v_0,v_1,\dots$ of distinct vertices such that $1\le |i-j|\le k$ implies that $v_i{v}_j$ is an edge), (3.) the vertex set of every $2$-edge colored countably infinite complete graph can be partitioned into $4$ monochromatic squares of paths, but not necessarily into $3$, (4.) the vertex set of every $2$-edge colored complete graph on ${\omega }_1$ can be partitioned into $2$ monochromatic paths with distinct colors.