×

On chromatic graphs. (Hungarian) Zbl 0152.41201

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

MSC:

05C15 Coloring of graphs and hypergraphs

Keywords:

topology
PDFBibTeX XMLCite