Perfectly contractile graphs (Q803147): Difference between revisions

Let f be a k-colouring of a graph G, \(1\leq i\neq j\leq k\), and H a connected component of the subgraph induced in G by \(f^{-1}(i)\cup f^{-1}(j)\). A new k-colouring g of G, which is said to be obtained from f by a k-switching, is defined by \(g(x)=f(x)\), if \(x\not\in H\); \(g(x)=i\), if \(x\in H\) and \(f(x)=j\); \(g(x)=j\), if \(x\in H\) and \(f(x)=i\). Two k- colourings f and g of G are said to be k-equivalent if there exists a sequence \(f_ 0,f_ 1,...,f_ s\) of k-colourings of G with \(f_ 0=f,f_ s=g\), and for each \(i=1,2,...,s\) \(f_ i\) is obtained from \(f_{i-1}\) by a k-switching. The purpose of this paper is to find which perfect graphs G have the property that, for every \(k\geq \gamma (G)\), the chromatic number of G, all k-colourings of G are k-equivalent. In this paper a new hereditary class of perfect graphs, namely the class of perfectly contractile graphs, which satisfy the above property is defined. It is shown that Gavril's clique separable graphs (hence also i- triangulated graphs), Chvátal's perfectly orderable graphs (hence also cotriangulated and comparability graphs), are perfectly contractible. The unique colorability of perfectly contractile graphs is investigated obtaining in the particular case of comparability graphs a generalization of a result by \textit{I. Rabinovitch} [Aequationes Math. 17, 41-43 (1978; Zbl 0397.06001)]. In the last section of the paper it is shown, among other examples and open problems, that not all perfectly contractile graphs are in \(Bip^*\), a class of perfect graphs invented by Chvátal.