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.

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Chao, C.Y.; Whitehead, E.G., On chromatic equivalence of graphs, (), 121-131
[2] 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
[3] Koh, K.M.; Teo, C.P., Some results on chromatically unique graphs, (), 258-262 · Zbl 0940.05502
[4] Koh, K.M.; Teo, K.L., The search for chromatically unique graphs, Graphs combin., 6, 259-285, (1990) · Zbl 0727.05023
[5] 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
[6] 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
[7] 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
[8] Tomescu, I., On 3-colourings of bipartite p-threshold graphs, J. graph theory, 11, 327-338, (1987) · Zbl 0662.05024
[9] Whitehead, E.G.; Zhao, L.C., Cutpoints and the chromatic polynomial, J. graph theory, 8, 371-377, (1984) · Zbl 0551.05041
[10] Whitney, H., A logical expansion in mathematics, Bull. amer. math. soc., 39, 572-579, (1932) · JFM 58.0605.08
[11] Wong, P.K., Cages - a survey, J. graph theory, 6, 1-22, (1982) · Zbl 0488.05044
[12] 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.