Complete Solution To Chromatic Uniqueness Of K 4 -Homeomorphs With Girth 9

Abstract

For a graph G , let P ( G; ) denote the chromatic polynomial of G . Two graphs G and H are chromatically equivalent (or simply

-equivalent), denoted by G

H , if P ( G; ) = P ( H; ) . A graph G is chromatically unique (or simply

-unique) if for any graph H such as H

G , we have H

= G , i.e. H is isomorphic to G . A K 4 -homeomorph is a subdivision of the complete graph K 4 . In this paper, we completely determine the chromaticity of K 4 -homeomorphs which has girth 9, and give su¢ cient and necessary condition for the graphs in the family to be chromatically unique