For a graph and positive integer , the exact distance- graph is the graph with vertex set and with an edge between vertices and if and only if and have distance . Recently, there has been an effort to obtain bounds on the chromatic number of exact distance- graphs for from certain classes of graphs. In particular, if a graph has tree-width , it has been shown that for odd , and for even . We show that if is chordal and has tree-width , then $\chi(G^{[\natural p]}) \in (p, t^2)p\chi(G^{[\natural p]}) \in (p, t^2 \Delta(G))p$. If we could show that for every graph of tree-width there is a chordal graph of tree-width which contains as an isometric subgraph (i.e., a distance preserving subgraph), then our results would extend to all graphs of tree-width . While we cannot do this, we show that for every graph of genus there is a graph which is a triangulation of genus and contains as an isometric subgraph.

生成讲解博客的中文版本

生成AI智能校验的中文版本