We prove a generalisation of Bollobás' classical result on the asymptotics of the chromatic number of the binomial random graph to the stochastic block model. In addition, by allowing the number of blocks to grow, we determine the chromatic number in the Chung-Lu model. Our approach is based on the estimates for the weighted independence number, where weights are specifically designed to encapsulate inhomogeneities of the random graph.
@article{10_37236_10728,
author = {Mikhail Isaev and Mihyun Kang},
title = {On the chromatic number in the stochastic block model},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {2},
doi = {10.37236/10728},
zbl = {1519.05076},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10728/}
}
TY - JOUR
AU - Mikhail Isaev
AU - Mihyun Kang
TI - On the chromatic number in the stochastic block model
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/10728/
DO - 10.37236/10728
ID - 10_37236_10728
ER -
%0 Journal Article
%A Mikhail Isaev
%A Mihyun Kang
%T On the chromatic number in the stochastic block model
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/10728/
%R 10.37236/10728
%F 10_37236_10728
Mikhail Isaev; Mihyun Kang. On the chromatic number in the stochastic block model. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/10728
