Multiset Colorings of Random Graphs Across Density Regimes

Abstract

We show that almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts. Equivalently, for $G\sim G(n,1/2)$, $\chi_m(G)\le3$ with high probability, improving the previously known bound of five. Here $\chi_m(G)$ denotes the multiset chromatic number of $G$, the minimum number of parts in a vertex partition whose neighbor-count vectors distinguish every pair of adjacent vertices. In fact, the three-part bound holds for every fixed $0.185<p<0.509$. More generally, for every fixed $p\in(0,1)$, $G\sim G(n,p)$ satisfies $\chi_m(G)\le4$ with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial--Radhakrishnan theory of essential covers. We also determine how $\chi_m(G)$ grows when the graph is polynomially close to complete. For every fixed $\beta\in(0,1)$ and $G\sim G\!\left(n,1-n^{-(1-\beta)}\right)$, with high probability $\frac{2}{\beta}\le \chi_m(G)\le \left\lfloor\frac{2}{\beta}\right\rfloor+5$. Thus $\chi_m(G)=2/\beta+O(1)$. The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov'asz Local Lemma.