Contents Online

# Journal of Combinatorics

## Volume 9 (2018)

### Number 3

### Bounded monochromatic components for random graphs

Pages: 411 – 446

DOI: http://dx.doi.org/10.4310/JOC.2018.v9.n3.a1

#### Authors

#### Abstract

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

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