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 (21:876)****[2]**P. Erdös and A. Hajnal,*On chromatic number of graphs and set systems*, Acta Math. Acad. Sci. Hungar.**17**(1966), 61-69. MR**0193025 (33:1247)****[3]**P. Erdös and J. Spencer,*Probabilistic methods in combinatorics*, Akadémiai Kiadó, Budapest; North-Holland, Amsterdam; Academic Press, New York, 1974. MR**0382007 (52:2895)****[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 and New York, 1971, pp. 97-99. MR**0277392 (43:3125)****[5]**L. Lovász,*On chromatic number of finite set-systems*, Acta Math. Acad. Sci. Hungar.**19**(1968), 59-67. MR**0220621 (36:3673)****[6]**J. Nešetřil and V. 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-512. MR**0409259 (53:13019)****[7]**-,*Partition of subgraphs*, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), Academia, Prague, 1975, pp. 413-423. MR**0363962 (51:217)****[8]**-,*A short proof of the existence of highly chromatic graphs without short cycles*, J. Combinatorial Theory Ser. B (to appear).**[9]**-,*Ramsey property of classes of graphs without forbidden complete subgraphs*, J. Combinatorial Theory**20**(1976), 243-249. MR**0412004 (54:133)****[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