Recolouring weakly chordal graphs and the complement of triangle-free graphs

Abstract: For a graph

G

, the

k

-recolouring graph

m a t h c a l R_{k} (G)

is the graph whose vertices are the

k

-colourings of

G

and two colourings are joined by an edge if they differ in colour on exactly one vertex. We prove that for all

n g e 1

, there exists a

k

-colourable weakly chordal graph

G

where

m a t h c a l R_{k + n} (G)

is disconnected, answering an open question of Feghali and Fiala. We also show that for every

k

-colourable

3 K_{1}

-free graph

G

,

m a t h c a l R_{k + 1} (G)

is connected with diameter at most

4 | V (G) |

.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Recolouring weakly chordal graphs and the complement of triangle-free graphs