Colouring powers and girth

Abstract

Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi (G^t)$, the chromatic number of the $t$th power of $G$? For $t\ge 3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $d\to \infty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.

15 pages, 2 figures, 2 tables; from v1 to v2, one section removed, one theorem improved

Cited by in corpus (2)

• Distance colouring without one cycle length
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers