Erdős–Burr conjecture

Let G be a simple graph. It follows from Ramsey's theorem that there exists a least integer r(G), the Ramsey number of G, such that any complete graph on at least r(G) vertices whose edges are coloured red or blue contains a monochromatic copy of G.

In 1973, Erdős and Burr made the following conjecture:

For every integer p there exists a constant c_p so that any graph G on n vertices in which every subgraph has a vertex of maximum degree at most p, has its Ramsey number bounded by r(G)leq c_p n

This conjecture has been settled in some special cases:

  • for p-arrangeable graphs, which includes graphs with bounded maximum degree, planar graphs and graphs with no subdivision of K_p;
  • for subdivided graphs.

See also


  • N. Alon (1994). Subdivided graphs have linear ramsey numbers. J. Graph Theory 18(4), 343–347.
  • S.A. Burr and P. Erdős (1975). On the magnitude of generalized Ramsey numbers for graphs. Colloquia Mathematica Societatis Janos Bolyai 10 Infinite and Finite Sets 1, 214–240.
  • G. Chen and R.H. Schelp (1993). Graphs with linearly bounded Ramsey numbers, J. Combin. Theory Ser. B 57(1), 138–149.
  • V. Chvátal, V. Rödl, E. Szemerdi, and W.T. Trotter Jr. (1983). The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34(3), 239–243.
  • N. Eaton (1998). Ramsey numbers for sparse graphs, Discrete Maths 185, 63–75.
  • R.L. Graham, V. Rödl, and A. Rucínski (2000). On graphs with linear Ramsey numbers, Journal of Graph Theory 35, 176–192.
  • R.L. Graham, V. Rödl, and A. Rucínski (2001). On bipartite graphs with linear Ramsey numbers, Paul Erdős and his mathematics, Combinatorica 21, 199–209.
  • Yusheng Li, C.C. Rousseau, and L. Soltés (1997). Ramsey linear families and generalized subdivided graphs, Discrete Mathematics, 269–275.
  • V. Rödl and R. Thomas (1991). Arrangeability and clique subdivisions, The mathematics of Paul Erdős (R.L. Graham and J. Nešetřil, eds.), Springer, pp. 236–239.

Search another word or see arrangeableon Dictionary | Thesaurus |Spanish
Copyright © 2014, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature