Journal of Combinatorics

Volume 14 (2023)

Number 4

The chromatic number of squares of random graphs

Pages: 507 – 537

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n4.a6

Authors

Kalyan Garapaty

Daniel Lokshtanov (Department of Computer Science, University of California, Santa Barbara, Calif., U.S.A.)

Hemanta K. Maji (Department of Computer Science, Purdue University, West Lafayette, Indiana, U.S.A.)

Alex Pothen (Department of Computer Science, Purdue University, West Lafayette, Indiana, U.S.A.)

Abstract

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

Received 7 December 2021

Accepted 1 August 2022

Published 14 April 2023