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.
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: DOI arXiv