##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 109.16502

**Autor: ** Erdös, Pál

**Title: ** On circuits and subgraphs of chromatic graphs (In English)

**Source: ** Mathematika, London 9, 170-175 (1962).

**Review: ** A graph is k-colorable if its points can be colored using k colors in such a way that no two points of the same color are adjacent. The chromatic number of a graph is k if it is k-colorable but not (k-1)-colorable. Let g_{k} (n) be the largest integer for which there is a graph of n points of chromatic number k and girth (minimum cycle length) g_{k} (n). Let f(m,k; n) be the maximum chromatic number among all graphs of n points, every subgraph of which is k-colorable. Theorem I: For k \geq 4, g_{k} (n) \leq 1+2 log n/ log (k-2). Theorem 2: To every k there is an \epsilon > 0 so that if n > n_{0} (\epsilon , k) there exists a graph with n points and chromatic number k every subgraph of which having [\epsilon n] points is 3-colorable. Theorem 3: For m > 3 f(m,3; n) > c(n/m)^{1/3} [ log(n/2m)^{-1}].

**Reviewer: ** F.Harary

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag