The Chromatic Number of Graph Powers

Abstract

It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 + o (1)) d 2 if g = 3, 4, 5 or 6, and is Θ( d 2 / log d ) if g [ges ] 7. Extensions to higher powers are considered as well.