Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 152.41201
Autor: Erdös, Pál; Hajnal, András
Title: On chromatic graphs (In Hungarian)
Source: Mat. Lapok 18, 1-4 (1967).
Review: Authors' summary: ``A graph G is said to have property Tc if for every k and every k of its vertices x1,...,xk the subgraph G(x1,...,xk) spanned by the vertices x1,...,xk contains a set of independent vertices having ck elements. We show that for every c < 1/2 there is a graph G having property Tc and chromatic number \aleph0. Clearly a graph having property T ½ has chromatic number at most 2. The question is left open if for every m > \aleph0 and every c < 1/2 there is a graph G having m vertices, satisfying property Tc and of chromatic number m.''
Reviewer: Cs.Pogány
Classif.: * 05C15 Chromatic theory of graphs and maps
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag