Colouring exact distance graphs of chordal graphs

Abstract

For a graph $G=(V,E)$ and positive integer $p$, the exact distance-$p$ graph $G^{[♮p]}$ 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^{[♮p]})$ 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^{[♮p]})\in \mathcal{O}(p^{t-1})$ for odd $p$, and $\chi (G^{[♮p]})\in \mathcal{O}(p^t\Delta (G))$ for even $p$. We show that if $G$ is chordal and has tree-width $t$, then $\chi (G^{[♮p]})\in \mathcal{O}(p{t}^2)$ for odd $p$, and $\chi (G^{[♮p]})\in \mathcal{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.

11 pages, 2 figures. Versions 2 and 3 include minor changes, which arise from reviewers' comments

References in corpus (2)

• On Low Tree-Depth Decompositions
• Exact distance coloring in trees

Cited by in corpus (1)

• Exact distance coloring in trees