zbMATH — the first resource for mathematics

Some remarks on the chromatic uniqueness of graphs. (English) Zbl 0672.05033
A 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.
Reviewer: W.G.Brown

05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)