Some remarks on the chromatic uniqueness of graphs.

*(English)*Zbl 0672.05033A graph G is quasi-separable if it contains a complete subgraph H such that G-H is disconnected. A quasi-block is a maximal subgraph which is not quasi-separable.

“We shall consider the situation in which G consists of exactly 2 quasi- blocks \(Q_ 1\) and \(Q_ 2\). Suppose \(Q_ 1\cap Q_ 2=K_ n\). G is said to have property P if for every \(i=1,2\) there exists \(x_ i\in V(Q_ i)\) such that \(x_ i\) is adjacent to all vertices of \(Q_ 1\cap Q_ 2''\) and to at least one other vertex.

Remarks. (3) If G has property P, then G is not chromatically unique (i.e. there exists a graph H not isomorphic to G having the same chromatic polynomial as G). (4) If G is chromatically unique, and if \(Q_ 1\cap Q_ 2\) is a \(K_ 2\), then (ii) \(Q_ 1\) and \(Q_ 2\) are chromatically unique; and (iii) \(Q_ 1\) and \(Q_ 2\) are edge- transitive, and at least one is vertex-transitive.

Other results refer to a concept of “overlapping” which is not formally defined.

“We shall consider the situation in which G consists of exactly 2 quasi- blocks \(Q_ 1\) and \(Q_ 2\). Suppose \(Q_ 1\cap Q_ 2=K_ n\). G is said to have property P if for every \(i=1,2\) there exists \(x_ i\in V(Q_ i)\) such that \(x_ i\) is adjacent to all vertices of \(Q_ 1\cap Q_ 2''\) and to at least one other vertex.

Remarks. (3) If G has property P, then G is not chromatically unique (i.e. there exists a graph H not isomorphic to G having the same chromatic polynomial as G). (4) If G is chromatically unique, and if \(Q_ 1\cap Q_ 2\) is a \(K_ 2\), then (ii) \(Q_ 1\) and \(Q_ 2\) are chromatically unique; and (iii) \(Q_ 1\) and \(Q_ 2\) are edge- transitive, and at least one is vertex-transitive.

Other results refer to a concept of “overlapping” which is not formally defined.

Reviewer: W.G.Brown

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C40 | Connectivity |

05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |