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∼ G(n,1/2), χm(G)≤3 with high probability, improving the previously known bound of five. Here χ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∈(0,1), G∼ G(n,p) satisfies χm(G)≤4 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 χm(G) grows when the graph is polynomially close to complete. For every fixed β∈(0,1) and G∼ G (n,1−n−(1−β)), with high probability 2/β≤ χm(G)≤ ⌊2/β⌋+5. Thus χm(G)=2/β+O(1). The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov'asz Local Lemma.
Related
- Density regions, integer certificates and packing colorings of distance graphs
- Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
- Graphs versus loopless digraphs with a given degree sequence, and convergence of uniformly random graphs at every density
- Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
BibTeX
@misc{ahadi2026multiset,
title = {{Multiset Colorings of Random Graphs Across Density Regimes}},
author = {Arash Ahadi and Sharareh Alipour},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23362},
eprint = {2609.23362},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23362},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Multiset Colorings of Random Graphs Across Density Regimes
AU - Arash Ahadi
AU - Sharareh Alipour
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23362
UR - https://arxiv.org/abs/2609.23362
AB - 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∼ G(n,1/2), χ_m(G)≤3 with high probability, improving the previously known bound of five. Here χ_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∈(0,1), G∼ G(n,p) satisfies χ_m(G)≤4 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 χ_m(G) grows when the graph is polynomially close to complete. For every fixed β∈(0,1) and G∼ G (n,1−n^−(1−β)), with high probability 2/β≤ χ_m(G)≤ ⌊2/β⌋+5. Thus χ_m(G)=2/β+O(1). The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov'asz Local Lemma.
ER -