Contents Online

# 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

#### 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

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