Exact distance coloring in trees

Nicolas Bousquet (1) , Louis Esperet (1) , Ararat Harutyunyan (2) , Rémi de Joannis de Verclos (1)

1 G-SCOP_OC - Optimisation Combinatoire
2 IMT - Institut de Mathématiques de Toulouse UMR5219

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.

Mots clés: graph; trees

Domaines: Informatique [cs]; Mathématique discrète [cs.DM]

Nicolas Bousquet, Louis Esperet, Ararat Harutyunyan, Rémi de Joannis de Verclos. Exact distance coloring in trees. Combinatorics, Probability and Computing, 2019, 28 (2), pp.177-186. ⟨10.1017/S0963548318000378⟩. ⟨hal-01525789⟩