Exact Distance Colouring in Trees

Source abstract

For an integer q ⩾ 2 and an even integer d , consider the graph obtained from a large complete q -ary tree by connecting with an edge any two vertices at distance exactly d in the tree. This graph has clique number q + 1, and the purpose of this short note is to prove that its chromatic number is Θ(( d log q )/log d ). It was not known that the chromatic number of this graph grows with d . As a simple corollary of our result, we give a negative answer to a problem of van den Heuvel and Naserasr, asking whether there is a constant C such that for any odd integer d , any planar graph can be coloured with at most C colours such that any pair of vertices at distance exactly d have distinct colours. Finally, we study interval colouring of trees (where vertices at distance at least d and at most cd , for some real c > 1, must be assigned distinct colours), giving a sharp upper bound in the case of bounded degree trees.