##
**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), G_{n} 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 G_{n} for which H(G_{n})/K (G_{n}) > cn(log n)^{-2} and for every G_{n} H(G_{n})/K(G_{n}) < cn(log n)^{-2}. By the methods of this paper it could in fact be proved that **liminf**_{n ––> oo} **(****max**_{Gn} {H(G_{n}) \over K(G_{n})} / {n \over (log n)^{2}} **)** \geq {(log 2)^{2} \over 4} and **limsup**_{n ––> oo} **(****max**_{Gn} {H(G_{n}) \over K(G_{n})} / {n \over (log n)^{2}} **)** \leq (log 2)^{2}. The author conjectures that

**lim**_{n ––> oo} **(****max**_{Gn} {H(G_{n}) \over K(G_{n})} / {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 **lim**_{k ––> oo} {f(2,k) \over k^{3}} = 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