zbMATH — the first resource for mathematics

On the sum of all distances in chromatic blocks. (English) Zbl 0789.05036
The author has constructed 2-connected \(k\)-chromatic graphs of order \(n\) with the maximum sum of all distances between their vertices. The extremal graphs are cycles and complete graphs as well as some of their modifications. Also several auxiliary results are given on chromatic critical graphs and blocks.

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Birkhoff, Ann. Math. (2) 14 pp 42– (1912)
[2] Dirac, J. Reine Angewandte Mathematik 228 pp 204– (1967)
[3] Lazebnik, J. Graph Theory 13 pp 203– (1989)
[4] Lazebnik, Discrete Math. 87 pp 53– (1991)
[5] Combinatorial problems and exercises. Akadémiai Kiadó, Budapest (1979).
[6] Plummer, Trans. Am. Math. Soc. 1 134 pp 85– (1968)
[7] Read, J. Combinat. Theory 4 pp 52– (1968)
[8] Tomescu, Discrete Math. 1 pp 351– (1972)
[9] Tomescu, J. Graph Theory 14 pp 101– (1990)
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.