On the Chromatic Number in the Stochastic Block Model

Mikhail Isaev; Mihyun Kang

doi:10.37236/10728

On the Chromatic Number in the Stochastic Block Model

Mikhail Isaev, Mihyun Kang

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

Abstract

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 encapsu-late inhomogeneities of the random graph.

Original language	English
Article number	P2.56
Journal	Electronic Journal of Combinatorics
Volume	30
Issue number	2
DOIs	https://doi.org/10.37236/10728
Publication status	Published - 2023

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Theoretical Computer Science
Geometry and Topology
Computational Theory and Mathematics
Applied Mathematics

Fields of Expertise

Information, Communication & Computing

Access to Document

10.37236/10728Licence: CC BY-ND 4.0

Cite this

@article{10276bab481d4732bb21ef8f35d4a11c,

title = "On the Chromatic Number in the Stochastic Block Model",

abstract = "We prove a generalisation of Bollob{\'a}s{\textquoteright} 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 encapsu-late inhomogeneities of the random graph.",

author = "Mikhail Isaev and Mihyun Kang",

note = "Publisher Copyright: {\textcopyright} The authors.",

year = "2023",

doi = "10.37236/10728",

language = "English",

volume = "30",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "2",

}

TY - JOUR

T1 - On the Chromatic Number in the Stochastic Block Model

AU - Isaev, Mikhail

AU - Kang, Mihyun

PY - 2023

Y1 - 2023

N2 - 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 encapsu-late inhomogeneities of the random graph.

AB - 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 encapsu-late inhomogeneities of the random graph.

UR - http://www.scopus.com/inward/record.url?scp=85163761498&partnerID=8YFLogxK

U2 - 10.37236/10728

DO - 10.37236/10728

M3 - Article

AN - SCOPUS:85163761498

SN - 1077-8926

VL - 30

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

M1 - P2.56

ER -

On the Chromatic Number in the Stochastic Block Model

Abstract

ASJC Scopus subject areas

Fields of Expertise

Access to Document

Other files and links

Cite this