Recolouring weakly chordal graphs and the complement of triangle-free graphs (Q2065883): Difference between revisions

Let \(G\) be a graph and let \(\mathcal{C}\) be the set of all \(k\)-colorings of \(G\). The \(k\)-recoloring graph of \(G\), \({\mathcal{R}}_k(G)\), is a graph with \(V({\mathcal{R}}_k(G))={\mathcal{C}}\) and \(c_1,c_2 \in \mathcal{C}\) are adjacent in \({\mathcal{R}}_k(G)\) if and only if there is exactly one vertex \(x \in V(G)\) with \(c_1(x)\neq c_2(x)\) and \(c_1(y)=c_2(y)\) for any \(y \in V(G)\setminus \{x\}\). It was showed by \textit{C. Feghali} and \textit{J. Fiala} [ibid. 343, No. 3, Article ID 111733, 6 p. (2020); Zbl 1432.05040)] that there exists a \(k\)-colorable weakly chordal graph \(G\) such that \({\mathcal{R}}_{k+1}(G)\) is not connected. A generalization of this result is one of the main results of the paper. It is proved that for any \(n \geq 1\), there exists a \(k\)-colorable weakly chordal graph \(G\) such that \({\mathcal{R}}_{k+n}(G)\) is not connected. The result is proved by showing that there exists \((k+n)\)-coloring \(c\) of \(G\) such that \(\{c(x); x \in N[v]\}=\{1,2,\ldots ,k+n\}\) for every vertex \(v \in V(G)\), which shows that \(c\) is an isolated vertex of \({\mathcal{R}}_{k+n}(G)\). On the other hand, there also exist \(k\)-colorable graphs \(G\) such that \({\mathcal{R}}_{k+1}(G)\) is connected. In this paper the author presents another family of such graphs. It is proved that for any \(k\)-colorable \(3K_1\)-free graph \(G\) it holds that \({\mathcal{R}}_{k+1}(G)\) is connected with diameter at most \(4|V(G)|\).