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