## 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