Skip to content
Preprint

Multiset Colorings of Random Graphs Across Density Regimes

Sep 2026 · 0 citations · 18 references
Mathematics

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.

View source

Similar papers

Preprint Sep 2026

Sub-quorum colorings of graphs

A sub-quorum coloring is a partial vertex coloring in which every colored vertex sees at least half of its colored closed neighborhood in its own color. We study the maximum number of colors $\psq(G)$ from structural, algorithmic and extremal viewpoints. Every $2$-independent set yields a sub-quorum coloring, so $\psq(...

Hao Ma, Rafik Sahbi, Wen-Lin Zhang · 0 citations
Preprint Oct 2026

Spectral Extremal 1-Planar Graphs with Bounded Pentagon Packing

Let $\mathcal P_1$ denote the class of 1-planar graphs and let $tC_5$ be the disjoint union of $t$ copies of $C_5$. For every fixed $t\ge3$ and all sufficiently large $n$, we determine the unique $n$-vertex $tC_5$-free graph in $\mathcal P_1$ with maximum adjacency spectral radius, answering Problem 1 of Li, Wang and Z...

Zhan-He Zhang · 0 citations
Preprint Sep 2026

Spectral bipartiteness in generalized odd graphs of diameter three

For a graph $G$ of order $n$, put $\sigma(G)=(\lambda_1(G)+\lambda_n(G))/n$. We determine the first three largest values of this invariant among nonbipartite distance-regular graphs of diameter three and odd girth at least seven. The unique maximizer is the folded $7$-cube, with value $1/32$; the unique second maximize...

Qi Zhou · 0 citations
Preprint Aug 2026

Rainbow Tur\'an numbers for paths of length four

Given a set $V$ of $n$ vertices and an integer $k\ge1$, our goal is to maximize the number of edges in graphs $G_1, G_2, \ldots, G_k$, defined on $V$, under the constraint that the union of all graphs, thought of as a multi-graph, does not contain a rainbow copy of the path $P_5$ on $5$ vertices, that is, a copy of $P_...

Sylwia Antoniuk, Andrzej Grzesik, Magdalena Prorok et al. · 0 citations
Preprint Sep 2026

Graph Coloring with Color Preferences

We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its ori...

Tomohiro Koana, Y. Oh, Hirotaka Yoneda · 0 citations
Preprint Aug 2026

On the Maximum Number of Vertices that Belong to Every Metric Basis

Metric bases of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. In this paper, we concentrate on the existence of vertices in a graph $G$ that belong to all metric bases of $G$. We call these basis forced vertices, and denote the number of them...

Anni Hakanen, Ville Junnila, T. Laihonen et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.