##
**Zentralblatt MATH**

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

**Zbl.No: ** 704.05020

**Autor: ** Erdös, Paul; Kubicka, Ewa; Schwenk, Allen J.

**Title: ** Graphs that require many colors to achieve their chromatic sum. (In English)

**Source: ** Combinatorics, graph theory, and computing, Proc. 20th Southeast Conf., Boca Raton/FL (USA) 1989, Congr. Numerantium 71, 17-28 (1990).

**Review: ** [For the entire collection see Zbl 688.00003.]

The chromatic sum \Sigma(G) of a graph G is the minimum sum \Sigma c(v) taken over all proper vertex-colourings c of G using positive integers, i.e. c: V(G) ––> N, and c(v)\ne c(w) whenever (v,w) in E(G). A proper colouring c is called best, if \Sigma c(v) = \Sigma(G). The paper gives a constructive proof of the unexpected property, that for any k \geq 2 and any positive integer t there exist k-chromatic graphs for which any best colouring must use at least k+t colours. For trees (k = 2) this was obtained in an earlier paper by *E. Kubicka* and *A. J. Schwenk* [Proc. 17th Ann. ACM Comp. Sci. Conf., ACM Press, 39- 45 (1989)]. To obtain small graphs G in terms of k and t is the main object of the paper, and for t = 1 the optimum is achieved.

**Reviewer: ** B.Toft

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

05C35 Extremal problems (graph theory)

**Keywords: ** chromatic sum

**Citations: ** Zbl 688.00003

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag