zbMATH — the first resource for mathematics

The number of shortest cycles and the chromatic uniqueness of a graph. (English) Zbl 0770.05064
Authors’ abstract: For a graph \(G\), let \(g(G)\) and \(\sigma_ g(G)\) denote, respectively, the girth of \(G\) and the number of cycles of length \(g(G)\) in \(G\). In this paper, we first obtain an upper bound for \(\sigma_ g(G)\) and determine the structure of a 2-connected graph \(G\) when \(\sigma_ g(G)\) attains the bound. These extremal graphs are then more-or-less classified, but one case leads to an unsolved problem. The structural results are finally applied to show that certain families of graphs are chromatically unique.

05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Chao, Lecture Notes Math. 642 pp 121– (1978)
[2] The Petersen graph is uniquely determined by its chromatic polynomial. Preprint (1988).
[3] Homobono, Discrete Math. 76 pp 37– (1989)
[4] An improved method for computing the chromatic polynomials of sparse graphs. Research Report CORR 87-20, Department of Combinatorial and Optimization, University of Waterloo (1987).
[5] Read, Recent advances in chromatic polynomial theory
[6] and , Chromatic polynomials. Selected Topics in Graph Theory 3, Academic Press, New York (1988), 15–42.
[7] Salzberg, Discrete Math. 58 pp 285– (1986)
[8] Singleton, Am. Math. Monthly 75 pp 42– (1968)
[9] Teo, J. Graph Theory 14 pp 89– (1990)
[10] Whitehead, J. Graph Theory 8 pp 371– (1984)
[11] Whitney, Ann. Math. 33 pp 688– (1932)
[12] Wong, J. Graph Theory 6 pp 1– (1982)
[13] Zeros of chromatic polynomials. Combinatorial Surveys: Proceedings of the 6th British Combinatorics Conference. Academic Press, London (1977) 199–223.
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.