The chromatic number of squares of random graphs

In a recent article, Cheng, Maji and Pothen [3] consider squares of sparse Erdős–Rényi graphs $G(n, p)$ with $p = \Theta (1/n)$ as interesting benchmark instances to evaluate parallel algorithms that color the input graph in the context of estimating a sparse Jacobian for optimization. (Here $n$ is the number of vertices in the graph and every edge is included independently with probability $p$.) These authors prove that if $G$ is sampled from $G(n, p)$ with $p = \Theta (1/n)$, then with high probability, the chromatic number of the square graph $G^2$ lies between $\Omega \left ( \frac{\log n}{\log \log n} \right)$ and $\mathcal{O}(\log n)$. In this work we obtain a tight $\Theta \left ( \frac{\log n}{\log \log n} \right)$ bound on the chromatic number of $G^2$. Along the way we also obtain asymptotically tight bounds for the maximum degree of the $k$-th power of graphs sampled from $G(n, p)$.

Keywords

chromatic number, powers of graphs, Erdos–Renyi random graphs, random binomial intersection graphs

2010 Mathematics Subject Classification

05C15, 68R10

Full Text (PDF format)

The work of Lokshtanov and Garapaty is supported by BSF award 2018302 and NSF award CCF-2008838.

The work of Maji is supported in part by NSF awards CNS-1618822 and CNS-2055605.

The work of Pothen is supported by NSF award CCF-1637534 and DOE award SC-0022260.

Received 7 December 2021

Accepted 1 August 2022

Published 14 April 2023