Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-07T14:08:18.090Z Has data issue: false hasContentIssue false
  • English
  • Français

Exact Distance Colouring in Trees

Part of: Graph theory

Published online by Cambridge University Press:  24 July 2018

NICOLAS BOUSQUET ,
LOUIS ESPERET ,
ARARAT HARUTYUNYAN  and
RÉMI DE JOANNIS DE VERCLOS
NICOLAS BOUSQUET
Affiliation:
Université Grenoble Alpes, CNRS, G-SCOP, Grenoble, France (e-mail: nicolas.bousquet@grenoble-inp.fr, louis.esperet@grenoble-inp.fr)
LOUIS ESPERET
Affiliation:
Université Grenoble Alpes, CNRS, G-SCOP, Grenoble, France (e-mail: nicolas.bousquet@grenoble-inp.fr, louis.esperet@grenoble-inp.fr)
ARARAT HARUTYUNYAN
Affiliation:
LAMSADE, University of Paris-Dauphine, Paris, France (e-mail: ararat.harutyunyan@dauphine.fr)
RÉMI DE JOANNIS DE VERCLOS
Affiliation:
Radboud University Nijmegen, Netherlands (e-mail: r.deverclos@math.ru.nl)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

MSC classification

Primary: 05C15: Coloring of graphs and hypergraphs
Secondary: 05C10: Planar graphs; geometric and topological aspects of graph theory

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 2 , March 2019 , pp. 177 - 186
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

†

The authors were partially supported by ANR Projects STINT (anr-13-bs02-0007) and GATO (anr-16-ce40-0009-01), and LabEx PERSYVAL-Lab (anr-11-labx-0025-01) and LabEx CIMI

References

[1] de Grey, A. D. N. J. (2018) The chromatic number of the plane is at least 5. arXiv:1804.02385Google Scholar
[2] van den Heuvel, J., Kierstead, H. A. and Quiroz, D. (2016) Chromatic numbers of exact distance graphs. J. Combin. Theory Ser. B. arXiv:1612.02160Google Scholar
[3] Kloeckner, B. R. (2015) Coloring distance graphs: A few answers and many questions. Geombinatorics 24 117–134.Google Scholar
[4] Nešetřil, J. and Ossona de Mendez, P. (2012) Sparsity: Graphs, Structures, and Algorithms, Springer.Google Scholar
[5] Nešetřil, J. and Ossona de Mendez, P. (2015) On low tree-depth decompositions. Graphs Combin. 31 1941–1963.Google Scholar
[6] Parlier, H. and Petit, C. (2017) Chromatic numbers for the hyperbolic plane and discrete analogs. arXiv:1701.08648Google Scholar
[7] Parlier, H. and Petit, C. (2016) Chromatic numbers of hyperbolic surfaces. Indiana Univ. Math. J. 65 1401–1423.Google Scholar
[8] Quiroz, D. (2017) Colouring exact distance graphs of chordal graphs. arXiv:1703.07008Google Scholar