Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [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.

Similar Articles

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

American Mathematical Society