2025/11/30 by Belavadi, Manoj, Cameron, Kathie
#05C15 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2512.00695
Given a k-colouring of a graph G and two of the colours, a Kempe chain is a connected component of the subgraph of G induced by the vertices coloured with one of these two colours. A Kempe swap changes one colouring into another by interchanging the colours of the vertices in a Kempe chain. Two colourings are Kempe equivalent if each can be obtained from the other by a series of Kempe swaps; the set of Kempe equivalent colourings is called a Kempe class. For a graph G, let χ(G) denote its chromatic number and let Ck(G) denote the set of all k-colourings of G. We say G is Kempe connected if for all k≥ χ(G), Ck(G) forms a Kempe class. For a graph H, graph G is called H-free if no induced subgraph of G is isomorphic to H. We prove that every H-free graph is Kempe connected if and only if H is an induced subgraph of the path on four vertices, P4. The graph 2K2 consists of four vertices and two edges which are not adjacent. We prove that for all p≥ 0, there is a k-colourable 2K2-free graph G such that Ck+p(G) does not form a Kempe class.