zbMATH — the first resource for mathematics

Three families of chromatically unique graphs. (English) Zbl 0808.05050
Summary: Let \(P(G)\) denote the chromatic polynomial of a graph \(G\). A graph \(G\) is said to be chromatically unique if \(P (G) = P (H)\) implies that \(H\) is isomorphic to \(G\). We prove that a graph (resp., a bipartite graph) obtained from \(K_{2, 4} \cup P_ s\) \((s \geq 3)\) (resp., \(K_{33} \cup P_ s\) \((s \geq 7)\)) by identifying the end vertices of the part \(P_ s\) with any two vertices of the complete bipartite graph \(K_{2, 4}\) (resp., \(K_{3, 3})\) is chromatically unique. We also show that a bipartite graph obtained from \((K_{3, 3}-e) \cup P_ s\) \((s \geq 5)\) where \(e\) is an edge of \(K_{3, 3,}\), by identifying the end vertices of the path \(P_ s\) with two nonadjacent vertices of \(K_{3, 3}-e\) is chromatically unique.

05C15 Coloring of graphs and hypergraphs