Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 573.05021
Autor: Erdös, Paul
Title: Problems and results on chromatic numbers in finite and infinite graphs. (In English)
Source: Graph theory with applications to algorithms and computer science, Proc. 5th Int. Conf., Kalamazoo/Mich. 1984, 201-213 (1985).
Review: [For the entire collection see Zbl 564.00004.]
In this paper some old and recent problems and results on chromatic numbers in finite and infinite graphs are discussed. For example: Let G be n-chromatic and the smallest odd circuit of which is 2k+1. Is it then true that the number of vertices of G is greater than nck, where ck tends to infinity together with k? (Hajnal, Sauer and Erdös). Other authors of the problems and results quoted in this paper are El-Zahar, Baumgartner, Laver, Foreman, Shelah, Taylor, Galvin, Komjath, Rödl, Rothschild, Graham, Fan Chung, Simonovits, Toft, Dirac, Folkman, Nesetril, Szemerédi, and Lovász.
Reviewer: I.Tomescu
Classif.: * 05C15 Chromatic theory of graphs and maps
05-02 Research monographs (combinatorics)
00A07 Problem books
Keywords: chromatic number; product of graphs; infinite chromatic number; generalized continuum hypothesis; edge critical graph
Citations: Zbl 564.00004
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag