On a probabilistic graph-theoretical method

Authors:
Jaroslav Nešetřil and Vojtěch Rödl

Journal:
Proc. Amer. Math. Soc. **72** (1978), 417-421

MSC:
Primary 05C65

DOI:
https://doi.org/10.1090/S0002-9939-1978-0507350-7

MathSciNet review:
507350

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a method by means of which one can simply prove the existence of sparse hypergraphs with large chromatic number. Moreover this method gives the full solution of an Erdös-Ore problem.

**[1]**P. Erdős,*Graph theory and probability*, Canad. J. Math.**11**(1959), 34–38. MR**0102081**, https://doi.org/10.4153/CJM-1959-003-9**[2]**P. Erdős and A. Hajnal,*On chromatic number of graphs and set-systems*, Acta Math. Acad. Sci. Hungar**17**(1966), 61–99. MR**0193025**, https://doi.org/10.1007/BF02020444**[3]**Paul Erdős and Joel Spencer,*Probabilistic methods in combinatorics*, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Probability and Mathematical Statistics, Vol. 17. MR**0382007****[4]**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****[5]**L. Lovász,*On chromatic number of finite set-systems*, Acta Math. Acad. Sci. Hungar.**19**(1968), 59–67. MR**0220621**, https://doi.org/10.1007/BF01894680**[6]**Jaroslav Nešetřil and Vojtěch Rödl,*Type theory of partition properties of graphs*, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 405–412. MR**0409259****[7]**Miroslav Fiedler (ed.),*Recent advances in graph theory*, Academia, Prague, 1975. MR**0363962****[8]**-,*A short proof of the existence of highly chromatic graphs without short cycles*, J. Combinatorial Theory Ser. B (to appear).**[9]**Jaroslav Nešetřil and Vojtěch Rödl,*The Ramsey property for graphs with forbidden complete subgraphs*, J. Combinatorial Theory Ser. B**20**(1976), no. 3, 243–249. MR**0412004****[10]**-,*Ramsey property of graphs without short odd cycles*, Math. Slovaca (to appear).**[11]**V. Rödl,*Generalization of Ramsey theorem and dimension of graphs*, Thesis, Charles University, Prague, 1973.

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

Retrieve articles in all journals with MSC: 05C65

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1978-0507350-7

Keywords:
Ordering,
partition,
graph

Article copyright:
© Copyright 1978
American Mathematical Society