On chromatic uniqueness of uniform subdivisions of graphs (Q1322194)

Two graphs \(G\) and \(H\) are said to be chromatically equivalent if their chromatic polnomials are the same. A graph \(G\) is said to be chromatically unique if every graph chromatically equivalent to \(G\) is isomorphic to \(G\). Let \(\sigma_ k (G)\) denote the number of \(k\)-cycles in a graph \(G\), and let \(g\) denote the girth of \(G\). It is shown that if \(G\) and \(H\) are chromatically equivalent, then \(\sigma_ k (G)= \sigma_ k (H)\) for all \(k\) such that \(g \leq k \leq (3/2) g-2\). This result is then combined with a theorem of the authors [J. Graph Theory 16, No. 1, 7-15 (1992; Zbl 0770.05064)] to show that all uniform subdivisions of some families of graphs, including the complete bipartite graphs and some cages, are chromatically unique.