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 Free Access

Abstract | References | Similar Articles | Additional Information

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

- 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** - 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**
A. Hajnal, R. Rado and V. T. Sós (Editors), - Oystein Ore,
*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753** - Peter Ungar and Blanche Descartes,
*Advanced Problems and Solutions: Solutions: 4526*, Amer. Math. Monthly**61**(1954), no. 5, 352–353. MR**1528740**, DOI https://doi.org/10.2307/2307489

*Infinite and finite sets*, (Proc. Colloq., Készthely, 1973, dedicated to P. Erdös), North-Holland, Amsterdam, 1975. MR

**50**#12526.

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

Retrieve articles in all journals with MSC: 05C15

Additional Information

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

Article copyright:
© Copyright 1977
American Mathematical Society