# zbMATH — the first resource for mathematics

On chromatic uniqueness of uniform subdivisions of graphs. (English) Zbl 0796.05034
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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory 05C38 Paths and cycles
Full Text:
##### References:
  Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, (), 121-131  Homobono, N.; Peyrat, C., Graphs such that every two edges are contained in a shortest cycle, Discrete math., 76, 37-44, (1989) · Zbl 0676.05054  Koh, K.M.; Teo, C.P., Some results on chromatically unique graphs, (), 258-262 · Zbl 0940.05502  Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs combin., 6, 259-285, (1990) · Zbl 0727.05023  Salzberg, P.M.; Lopez, M.A.; Giudici, R.E., On the chromatic uniqueness of bipartite graphs, Discrete math., 58, 285-294, (1986) · Zbl 0594.05034  Teo, C.P.; Koh, K.M., The chromaticity of complete bipartite graphs with at most one edge deleted, J. graph theory, 14, 89-99, (1990) · Zbl 0712.05027  Teo, C.P.; Koh, K.M., The number of shortest cycles and the chromatic uniqueness of a graph, J. graph theory, 16, 7-15, (1992) · Zbl 0770.05064  Tomescu, I., On 3-colourings of bipartite p-threshold graphs, J. graph theory, 11, 327-338, (1987) · Zbl 0662.05024  Whitehead, E.G.; Zhao, L.C., Cutpoints and the chromatic polynomial, J. graph theory, 8, 371-377, (1984) · Zbl 0551.05041  Whitney, H., A logical expansion in mathematics, Bull. amer. math. soc., 39, 572-579, (1932) · JFM 58.0605.08  Wong, P.K., Cages - a survey, J. graph theory, 6, 1-22, (1982) · Zbl 0488.05044  Woodall, D.R., Zeros of chromatic polynomials, (), 199-223 · Zbl 0357.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.