Frozen Colourings in $2K_2$-free graphs

Abstract

The reconfiguration graph of the $k$-colourings of a graph $G$, denoted $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two vertices of $\mathcal{R}_k(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 for every vertex $v \in 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, $\overline{G}$. A $k$-clique-partition $\mathcal{Q}$ of a graph $H$ is called frozen if for every vertex $v \in V(H)$, $v$ has a non-neighbour in each of the cliques of $\mathcal{Q}$ other than the one containing $v$.

The complement of the cycle on four vertices, $C_4$, is called $2K_2$. We give several infinite classes of $2K_2$-free graphs with frozen colourings. We give an operation that transforms a $k$-chromatic graph with a frozen $(k+1)$-colouring into a $(k+1)$-chromatic graph with a frozen $(k+2)$-colouring. The operation requires some restrictions on the graph, the colouring, and the frozen colouring. The operation preserves being $2K_2$-free. Using this we prove that for all $k \ge 4$, there is a $k$-chromatic $2K_2$-free graph with a frozen $(k+1)$-colouring. We prove these results by studying frozen clique partitions in $C_4$-free graphs.

We say a graph $G$ is recolourable if $R_{\ell}(G)$ is connected for all $\ell$ greater than the chromatic number of $G$. We prove that every 3-chromatic $2K_2$-free graph $G$ is recolourable and that for all $\ell$ greater than the chromatic number of $G$, the diameter of $R_{\ell}(G)$ is at most $14n$ where $n$ is the number of vertices of $G$.