Colouring exact distance graphs of chordal graphs

2017 
For a graph $G=(V,E)$ and positive integer $p$, the exact distance-$p$ graph $G^{[\natural 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^{[\natural 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^{[\natural p]}) \in \mathcal{O}(p^{t-1})$ for odd $p$, and $\chi(G^{[\natural 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^{[\natural p]}) \in \mathcal{O}(p t^2)$ for odd $p$, and $\chi(G^{[\natural p]}) \in \mathcal{O}(p t^2 \Delta(G))$ for even $p$.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    12
    References
    5
    Citations
    NaN
    KQI
    []