Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 156.22302
Autor: Erdös, Pál
Title: Some remarks on chromatic graphs (In English)
Source: Colloq. Math. 16, dedie a Franciszek Leja, 253-256 (1967).
Review: A graph G is said to have chromatic number k if its vertices can be partioned into k classes so that two vertices in the same class are not joined by an edge and such a partitioning into k-1 classes is not possible. The chromatic number of the graph G is denoted by H(G). A graph is called complete if each pair of vertices of the graph are joined by an edge. The number of vertices in the largest complete graphs which are subgraphs of the graph G is denoted by K(G), Gn always denotes a graph with exactly n vertices. It is shown that there exist strictly positive constants c and c' such that for every positive integer n there exists a graph Gn for which H(Gn)/K (Gn) > cn(log n)-2 and for every Gn H(Gn)/K(Gn) < cn(log n)-2. By the methods of this paper it could in fact be proved that liminfn ––> oo (maxGn {H(Gn) \over K(Gn)} / {n \over (log n)2} ) \geq {(log 2)2 \over 4} and limsupn ––> oo (maxGn {H(Gn) \over K(Gn)} / {n \over (log n)2} ) \leq (log 2)2. The author conjectures that
limn ––> oo (maxGn {H(Gn) \over K(Gn)} / {n \over (log n)2} ) exists.
In the last part of the paper the following interesting problems are stated: G(n; m) denotes a graph with n vertices and m edges. To determine the smallest integer f(l,k) for which there exists a graph G having f(l,k) edges and satisfying K(G) \leq l, H(G) = k. It is conjectured that limk ––> oo {f(2,k) \over k3} = C < oo. A set of vertices of a graph G is called independent if no two of them are joined. I(G) denotes the greatest integer for which there is a set of I(G) indepenent vertices in G. To determine g(n; k,l), the smallest integer for which there exists a G(n; g(n; k,l) satisfying I(G(n; g(n; k,l))) = I, K(G(n; g(n; k,l))) = k.
Reviewer: G.A.Dirac
Classif.: * 05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag