2024/09/20 by Manoj Belavadi, Belavadi, Manoj, Kathie Cameron +3 · 1 citation
Computer Science · #0C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2409.13161
openalex publication_date 2024/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The reconfiguration graph of the k-colourings of a graph G, denoted Rk(G), is the graph whose vertices are the k-colourings of G and two vertices of Rk(G) are joined by an edge if the colourings of G they correspond to differ in colour on exactly one vertex. A k-colouring of a graph G is called frozen if it is an isolated vertex in Rk(G); in other words, for every vertex v ∈ V(G), v is adjacent to a vertex of every colour different from its colour. A clique partition is a partition of the vertices of a graph into cliques. A clique partition is called a k-clique-partition if it contains at most k cliques. Clearly, a k-colouring of a graph G corresponds precisely to a k-clique-partition of its complement, G. A k-clique-partition Q of a graph H is called frozen if for every vertex v ∈ V(H), v has a non-neighbour in each of the cliques of Q other than the one containing v. The cycle on four vertices, C4, is sometimes called the square; its complement is called 2K2. We give several infinite classes of 2K2-free graphs with frozen colourings. We give an operation which transforms a k-chromatic graph with a frozen (k+1)-colouring into a (k+1)-chromatic graph with a frozen (k+2)-colouring. Our operation preserves being 2K2-free. It follows that for all k ≥ 4, there is a k-chromatic 2K2-free graph with a frozen (k+1)-colouring. We prove these results by studying frozen clique partitions in C4-free graphs. We say a graph G is recolourable if Rℓ(G) is connected for all ℓ greater than the chromatic number of G. We prove that every 3-chromatic 2K2-free graph is recolourable.