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 - OC
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
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.
Mots-clés : trees graph
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01525789
Contributeur : Louis Esperet <>
Soumis le : mardi 26 novembre 2019 - 12:26:18
Dernière modification le : vendredi 24 janvier 2020 - 14:40:21

Fichier

exact_distance.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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

Partager

Métriques

Consultations de la notice

247

Téléchargements de fichiers

27