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 o 0, d o t s, r - 1

. Extending results of Rado and answering questions of Rado, Gy'arf'as and S'ark"ozy 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^{t h}

powers of paths apart from a finite set (a

k^{t h}

power of a path is a sequence

v_{0}, v_{1}, d o t s

of distinct vertices such that

1 l e | i - j | l e 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

o m e g a_{1}

can be partitioned into

2

monochromatic paths with distinct colors.

Recommendations

Cites Work

Cited In (21)

This page was built for publication: Decompositions of edge-colored infinite complete graphs into monochromatic paths