The Chromatic Uniqueness of a Family of 6-Bridge Graphs

Let P(G, λ) denote the chromatic polynomial of a graph G. Two graphs G and H are chromatically equivalent, written G ∼ H, if P(G, λ )= P(H, λ). Ag raphG is chromatically unique, written χ−unique, if for any graph H, G ∼ H implies that G is isomorphic with H. In this paper we prove the chromatic uniqueness of a new family of 6-bridge graphs. All graphs considered here are finite, undirected and simple. For a graph G let V (G), E(G) ,v (G) ,e (G) ,g (G) ,P (G, λ) respectively be the vertex set, edge set, order, size, girth and chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent, and we write G ∼ H, if P (G, λ )= P (H, λ). Ag raphG is chromatically unique (or simply χ − unique )i fG ∼ H for any graph H such that G ∼ H. By a subdivision we mean an operation of replacing an edge of a graph by a path. If a graph H can be derived from G by a sequence of subdivisions, we say H is a subdivision of G. For each positive integer h, the graph G(h) obtained from G by replacing each edge of G with a path of length h is called the h-uniform subdivision of G. A chain in a graph G is a path in G in which every internal vertex has degree 2 in G. The operation that replaces a u − v chain by a an edge uv is called a chain-contraction. By contracting all maximal chains of a graph G, we arrive at multigraph M (G). Two graphs G and H are homeomorphic if M (G )= M (H). If G is homeomorphic to H, we also say G is a H-homeomorph.