×

On graphs with small subgraphs of large chromatic number. (English) Zbl 0581.05023

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 E. Szemerédi [Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS No.260, 399-401 (1978; Zbl 0413.05055)].
Reviewer: J.Mitchem

MSC:

05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0413.05055
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B., Erdös, P., Simonovits, M., Szemerédi, E.: Extremal graphs without large forbidden subgraphs. In: Advances in Graph Theory (Cambridge Comb. Conf. Trinity College, 1977). Ann. Discrete Math.3, 29–41 (1978) · Zbl 0375.05034
[2] Erdös, P.: Problems and results of graphs and hypergraphs: similarities and differences. In: Recent Progress in Ramsey Theory, edited by Nešetřil, J., Rödl, V. (Proc. Third Czechoslovak Symposium on Graph Theory, Prague 1982)
[3] Szemerédi, E.: Regular partitions of graphs. Proc. Colloq. Int. C.N.R.S., pp. 399–401 (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.