Erdős, Pál; Hajnal, András On chromatic graphs. (Hungarian) Zbl 0152.41201 Mat. Lapok 18, 1-4 (1967). Authors’ summary: “A graph \(G\) is said to have property \(T_c\) if for every \(k\) and every \(k\) of its vertices \(x_1,...,x_k\) the subgraph \(G(x_1,...,x_k)\) spanned by the vertices \(x_1,...,x_k\) contains a set of independent vertices having \(ck\) elements. We show that for every \(c < {1 \over 2}\) there is a graph \(G\) having property \(T_c\) and chromatic number \(\aleph_0\). Clearly a graph having property \(T_{1/2}\) has chromatic number at most 2. The question is left open if for every \(m > \aleph_0\) and every \(c < {1 \over 2}\) there is a graph \(G\) having \(m\) vertices, satisfying property \(T_c\) and of chromatic number \(m\).” Reviewer: Cs.Pogány Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 1 ReviewCited in 8 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:topology PDFBibTeX XMLCite \textit{P. Erdős} and \textit{A. Hajnal}, Mat. Lapok 18, 1--4 (1967; Zbl 0152.41201)