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