{"id":"arxiv/2609.23362","url":"https://arxiv.org/abs/2609.23362","tags":["math.CO"],"score":0,"title":"Multiset Colorings of Random Graphs Across Density Regimes","domain":"math.CO","source":"arxiv","authors":["Arash Ahadi","Sharareh Alipour"],"reviews":0,"subject":"math.CO","summary":"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)$, $χ_m(G)\\le3$ 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\\in(0,1)$,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}