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 gk (n) be the largest integer for which there is a graph of n points of chromatic number k and girth (minimum cycle length) gk (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, gk (n) \leq 1+2 log n/ log (k-2). Theorem 2: To every k there is an \epsilon > 0 so that if n > n0 (\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