COLORING POWERS AND GIRTH

摘要

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 tth power of G? For t >= 3, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as d -> infinity. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.