zbMATH — the first resource for mathematics

On upper estimates for the chromatic number of graphs. (Russian) Zbl 0677.05027
Tr. Inst. Mat. 10, 204-226 (1988).
Vertex colourings of finite simple undirected connected graphs are considered. Let f(n,g) denote the maximum chromatic number of a graph of diameter \(g+1\) with n vertices. A lower bound for f(n,g) is given. This bound improves a result of P. Erdős [Can. J. Math. 11, No.1, 34- 38 (1959; Zbl 0084.396)].
For some interesting classes of graphs non-trivial upper bounds of the chromatic numbers of graphs contained in these classes are found. These upper bounds are formulated in terms of the diameters of the graphs and in terms of the number of vertices of maximum complete subgraphs. Special results concern the class of circle graphs.
Reviewer: U.Baumann

05C15 Coloring of graphs and hypergraphs