On the chromatic number of subgraphs of a given graph

Author:
V. Rödl

Journal:
Proc. Amer. Math. Soc. **64** (1977), 370-371

MSC:
Primary 05C15

DOI:
https://doi.org/10.1090/S0002-9939-1977-0469806-4

MathSciNet review:
0469806

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that for arbitrary positive integers *m,n* there exists a such that if , then *G* contains either a complete subgraph of size *m* or a subgraph *H* with containing no . This gives an answer to a problem of Erdös and Hajnal.

**[1]**P. Erdős,*Problems and results in chromatic graph theory*, Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) Academic Press, New York, 1969, pp. 27–35. MR**0252273****[2]**P. Erdős,*Some unsolved problems in graph theory and combinatorial analysis*, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London, 1971, pp. 97–109. MR**0277392****[3]**A. Hajnal, R. Rado and V. T. Sós (Editors),*Infinite and finite sets*, (Proc. Colloq., Készthely, 1973, dedicated to P. Erdös), North-Holland, Amsterdam, 1975. MR**50**#12526.**[4]**Oystein Ore,*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753****[5]**Peter Ungar and Blanche Descartes,*Advanced Problems and Solutions: Solutions: 4526*, Amer. Math. Monthly**61**(1954), no. 5, 352–353. MR**1528740**, https://doi.org/10.2307/2307489

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
05C15

Retrieve articles in all journals with MSC: 05C15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1977-0469806-4

Keywords:
Graph,
subgraph,
triangle-free graph,
chromatic number

Article copyright:
© Copyright 1977
American Mathematical Society