On the chromatic number of graphons

Abstract

We extend Bollobas' classical result on the chromatic number of a binomial random graph to the exchangeable random graph model $\mathcal{G}(n,W)$ defined by a graphon $W:[0,1{]}^2\to [0,1]$, which is a symmetric measurable function. In the case when $W$ can be approximated by block graphons in ${\mathcal{L}}^{\infty }$-norm, we show that asymptotically optimal value of the number of colours required for $\mathcal{G}(n,W)$ is determined by colouring strategies that use a finite number of different types of colour classes. Furthermore, if $W$ is a block graphon with $k\times k$ blocks then $k$ types of colour classes are sufficient. We also show that if $W$ is block-increasing or block-Lipschitz then such colouring strategies that use $k$ types determine the chromatic number up to a multiplicative error of order $O(k^{-1})$.

References in corpus (3)

• Independent sets, cliques, and colorings in graphons
• The Chromatic Number of Dense Random Block Graphs
• On the chromatic number in the stochastic block model