On graphs with small subgraphs of large chromatic number (Q1068099): Difference between revisions

Theorem: For each positive constant c and positive integer k there exist positive integers \(f_ k(c)\) and \(n_ 0\) such that if \(G=(V,E)\) is any graph with \(| V| =n>n_ 0\) having the property that \(\chi\) (V,E- F)\(\geq k\) whenever \(| F| <cn^ 2\), then there exists a subgraph \(H=(V^ 1,E^ 1)\) of G with \(| V^ 1| \leq f_ k(c)\) such that \(\chi (H)=k\). This is a generalization suggested by Erdős of the following conjecture of Bollobás, Erdős, Simonovits, and Szemerédi: For each positive constant c there exists a constant g(c) such that if G is any graph which cannot be made 3-chromatic by the omission of \(cn^ 2\) edges, then G contains a 4-chromatic subgraph with at most g(c) vertices. The proof is based on the uniform density theorem of \textit{E. Szemerédi} [Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No.260, 399-401 (1978; Zbl 0413.05055)].