Colouring exact distance graphs of chordal graphs

Abstract

For a graph G = (V, E) and positive integer p, the exact distance-p graph G([hp]) is the graph with vertex set V and with an edge between vertices x and y if and only if x and y have distance p. Recently, there has been an effort to obtain bounds on the chromatic number chi(G([hp])) of exact distance -p graphs for G from certain classes of graphs. In particular, if a graph G has tree -width t, it has been shown that chi(G([hp]) is an element of 0(p(t-1)) for odd p, and chi(G([hp])) E O(pt Delta (G)) for even p. We show that if G is chordal and has tree-width t, then x(G([hp])) E O(p t(2)) for odd p, and chi(G([hp])) is an element of O(p t(2) Delta(G)) for even p.

If we could show that for every graph H of tree -width t there is a chordal graph G of tree-width t which contains H as an isometric subgraph (i.e., a distance preserving subgraph), then our results would extend to all graphs of tree -width t. While we cannot do this, we show that for every graph H of genus g there is a graph G which is a triangulation of genus g and contains H as an isometric subgraph. (C) 2019 Elsevier B.V. All rights reserved.