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.
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(...
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...
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...
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
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
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.