Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 194.25102
Autor: Erdös, Pál
Title: Problems and results in chromatic graph theory (In English)
Source: Proof Tech. Graph Theory, Proc. 2nd Ann Arbor Graph Theory Conf. 1968, 27-35 (1969).
Review: [For the entire collection see Zbl 193.28103.]
Several problems and results in graph theory are discussed mostly connected with chromatic numbers. Here I only state some of those questions which have been solved in the mean time. Hajnal proved that an \aleph1 chromatic graph contains for every n > n0 a circuit of n edges. Poft constructed a four chromatic critical graph having more than n2/16 edges and J. Spencer constructed a graph of n vertices which has more than n- log n/ log 2-c cliques of different sizes. Non of these results is published as yet.
Classif.: * 05C15 Chromatic theory of graphs and maps
00A07 Problem books
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag