Reconfiguration of vertex colouring and forbidden induced subgraphs

Abstract: The reconfiguration graph of the

k

-colourings, denoted

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 adjacent in

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

if they differ in colour on exactly one vertex. In this paper, we investigate the connectivity and diameter of

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

for a

k

-colourable graph

G

restricted by forbidden induced subgraphs. We show that

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

is connected for every

k

-colourable

H

-free graph

G

if and only if

H

is an induced subgraph of

P_{4}

or

P_{3} + P_{1}

. We also start an investigation into this problem for classes of graphs defined by two forbidden induced subgraphs. We show that if

G

is a

k

-colourable (

2 K_{2}

,

C_{4}

)-free graph, then

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

is connected with diameter at most

4 n

. Furthermore, we show that

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

is connected for every

k

-colourable (

P_{5}

,

C_{4}

)-free graph

G

.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Reconfiguration of vertex colouring and forbidden induced subgraphs