Bounded monochromatic components for random graphs

We consider vertex partitions of the binomial random graph $G_{n,p}$. For $np \to \infty$, we observe the following phenomenon: in any partition into asymptotically fewer than $\chi (G_{n,p})$ parts, i.e. $o(np \: / \log np)$ parts, one part must induce a connected component of order at least roughly the average part size.

Stated another way, we consider the $t$-component chromatic number, the smallest number of colours needed in a colouring of the vertices for which no monochromatic component has more than $t$ vertices. As long as $np \to \infty$, there is a threshold for $t$ around $\Theta (p^{-1} \log np)$: if $t$ is smaller then the $t$-component chromatic number is nearly as large as the chromatic number, while if $t$ is greater then it is around $n/t$.

For $0 \lt p \lt 1$ fixed, we obtain more precise information. We find something more subtle happens at the threshold $t = \Theta (\log n)$, and we determine that the asymptotic first-order behaviour is characterised by a non-smooth function. Moreover, we consider the $t$-component stability number, the maximum order of a vertex subset that induces a subgraph with maximum component order at most $t$, and show that it is concentrated in a constant length interval about an explicitly given formula, so long as $t = O(\log \log n)$.

We also consider a related Ramsey-type parameter and use bounds on the component stability number of $G_{n, 1/2}$ to describe its basic asymptotic growth.

Keywords

graph colouring, random graphs, component colouring, component stability

2010 Mathematics Subject Classification

05A16, 05C15, 05C80

Full Text (PDF format)

Supported by Veni (639.031.138) and Vidi (639.032.614) grants of the Netherlands Organisation for Scientific Research (NWO) as well as a Postdoctoral Fellowship of the Natural Sciences and Engineering Research Council of Canada (NSERC).

Received 14 May 2015

Published 18 May 2018