On chromatic uniqueness of uniform subdivisions of graphs

Abstract

Let σk(G) denote the number of cycles of length k in a graph G. In this paper, we first prove that if G and H are χ-equivalent graphs, then σk(G) = σk(H) for all k with g≤k≤ 3 2g - 2, w ere g is the girth of G. This result will then be incorporated with a structural theorem obtained in [7] to show that all uniform subdivisions of some families of graphs, including the complete bipartite graphs and certain cages, are χ-unique. © 1994.