Perfectly contractile graphs

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

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.

Recommendations

Cites work

Cited in

(28)

This page was built for publication: Perfectly contractile graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q803147)