Partitioning random graphs into monochromatic components

Deepak Bal, Louis DeBiasio

Published 2015-09-30Version 1

Erd\H{o}s, Gy\'arf\'as, and Pyber conjectured that every $r$-colored complete graph can be partitioned into at most $r-1$ monochromatic components; this is a strengthening of a conjecture of Lov\'asz and Ryser in which the components are only required to form a cover. An important partial result of Haxell and Kohayakawa says that $r$ components suffice for sufficiently large complete graphs. We extend these results from the setting of complete graphs to the setting of random graphs (and along the way, graphs with large minimum degree). In particular, we show that $r$-colored graphs with large minimum degree have a robust structure which gives us a partition into $r$ monochromatic components even after deleting any subset of vertices from a special linear sized set. We use this, together with the sparse regularity lemma, to determine the threshold for which every $r$-coloring of $G(n,p)$ can partitioned into $r$ monochromatic components.