The Chromatic Number of Dense Random Block Graphs

arXiv2007.07700MaRDI QIDQ6345155FDOQ6345155

Authors: Anders Martinsson, Konstantinos Panagiotou, Pascal Su, Miloš Trujić 

Publication date: 15 July 2020

Abstract: The chromatic number $chi(G)$ of a graph $G$, that is, the smallest number of colors required to color the vertices of $G$ so that no two adjacent vertices are assigned the same color, is a classic and extensively studied parameter. Here we consider the case where $G$ is a random block graph, also known as the stochastic block model. The vertex set is partitioned into $kinmathbbN$ parts $V_1,dotsc,V_k$, and for each $1leilejlek$, two vertices $uin{V}_i,vin{V}_j$ are connected by an edge with some probability $p_{ij}in(0,1)$ independently. Our main result pins down the typical asymptotic value of $chi(G)$ and establishes the distribution of the sizes of the color classes in optimal colorings. We discover that in contrast to the case of a binomial random graph $G(n,p)$, that corresponds to $k=1$ in our model, where the average size of a color class in an (almost) optimal coloring essentially coincides with the independence number, the block model reveals a more diverse picture: the "average" class in an optimal coloring is a convex combination of several types of independent sets that vary in total size as well as in the size of their intersection with each $V_i$, $1leilek$.

This page was built for publication: The Chromatic Number of Dense Random Block Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345155)