# zbMATH — the first resource for mathematics

Bounded monochromatic components for random graphs. (English) Zbl 1387.05190
Summary: We consider vertex partitions of the binomial random graph $$G_{n,p}$$. For $$np \rightarrow \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 \rightarrow \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 < p < 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.
##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C15 Coloring of graphs and hypergraphs 05C80 Random graphs (graph-theoretic aspects)
Full Text: