• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Exact Distance Colouring in Trees

Thumbnail
Ouvrir
exact_distance.pdf (163.4Kb)
Date
2019
Indexation documentaire
Probabilités et mathématiques appliquées
Subject
graph; trees
Nom de la revue
Combinatorics, Probability and Computing
Volume
28
Numéro
2
Date de publication
03-2019
Pages article
177-186
DOI
http://dx.doi.org/10.1017/S0963548318000378
URI
https://basepub.dauphine.fr/handle/123456789/20246
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Bousquet, Nicolas
74240 Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Esperet, Louis
74240 Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Harutyunyan, Ararat
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
De Joannis de Verclos, Rémi
115536 autre
Type
Article accepté pour publication ou publié
Résumé en anglais
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.