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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page