On a probabilistic graph-theoretical method

Nešetřil, Jaroslav; Rödl, Vojtěch

doi:10.1090/S0002-9939-1978-0507350-7

On a probabilistic graph-theoretical method
HTML articles powered by AMS MathViewer

by Jaroslav Nešetřil and Vojtěch Rödl PDF

Proc. Amer. Math. Soc. 72 (1978), 417-421 Request permission

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.

References

P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. MR 193025, DOI 10.1007/BF02020444
Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0382007
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
L. Lovász, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hungar. 19 (1968), 59–67. MR 220621, DOI 10.1007/BF01894680
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
Miroslav Fiedler (ed.), Recent advances in graph theory, Academia, Prague, 1975. MR 0363962

A short proof of the existence of highly chromatic graphs without short cycles

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 412004, DOI 10.1016/0095-8956(76)90015-0

Ramsey property of graphs without short odd cycles

Generalization of Ramsey theorem and dimension of graphs