{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:52Z","timestamp":1753893832247,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.\r\nA 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$.\r\nThe 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.\r\nWe 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$.<\/jats:p>","DOI":"10.37236\/13669","type":"journal-article","created":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T14:33:01Z","timestamp":1747924381000},"source":"Crossref","is-referenced-by-count":0,"title":["Frozen Colourings in $2K_2$-free graphs"],"prefix":"10.37236","volume":"32","author":[{"given":"Manoj","family":"Belavadi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kathie","family":"Cameron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elias","family":"Hildred","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2025,5,23]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v32i2p29\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v32i2p29\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,22]],"date-time":"2025-05-22T14:33:01Z","timestamp":1747924381000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v32i2p29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,23]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,4,11]]}},"URL":"https:\/\/doi.org\/10.37236\/13669","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2025,5,23]]},"article-number":"P2.29"}}