##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 677.05028

**Autor: ** Thomassen, Carsten; Erdös, Paul; Alavi, Yousef; Malde, Paresh J.; Schwenk, Allen J.

**Title: ** Tight bounds on the chromatic sum of a connected graph. (In English)

**Source: ** J. Graph Theory 13, No.3, 353-357 (1989).

**Review: ** A proper colouring of the vertices of the graph G assigns different colours to adjacent vertices. The chromatic sum \Sigma(G) of G is defined to be the smallest possible total over all vertices that can occur among all proper colourings of G using natural numbers for the colours.

For any graph G with n vertices and e edges the chromatic sum is at most n+e. In the paper tight bounds on the chromatic sum of a connected graph are determined: \lceil \sqrt{8e}\rceil \leq \Sigma(G) \leq \lfloor ^{3}/_{2} (e+1)\rfloor. For a disconnected graph G with no isolated vertices \lceil \sqrt{8e}\rceil \Sigma(G) \leq 3e holds.

**Reviewer: ** U.Baumann

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

**Keywords: ** proper colourings; chromatic sum

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag