Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

摘要

A k-colouring of a graph G = (V,E) is a mapping c: V →{1, 2,. . ., k} such that c(u) ≠ c(v) whenever uv is an edge. The reconfiguration graph of the kcolourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if they differ in colour on just one vertex of G. We introduce a class of k-colourable graphs, which we call k-colour-dense graphs. We show that for each k-colour-dense graph G, the reconfiguration graph of the ?-colourings of G is connected and has diameter O(V ~2), for all ? ≥ k + 1. We show that this graph class contains the k-colourable chordal graphs and that it contains all chordal bipartite graphs when k = 2. Moreover, we prove that for each k ≥ 2 there is a k-colourable chordal graph G whose reconfiguration graph of the (k +1)-colourings has diameter Θ(V 2).