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

• Erdős conjecture

References

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