Let G be a simple graph. It follows from Ramsey's theorem that there exists a least integer <math>r(G)</math>, the Ramsey number of G, such that any complete graph on at least <math>r(G)</math> 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 <math>c_p</math> 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 <math>r(G)\leq c_p n</math>
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 <math>K_p</math>;
- for subdivided graphs.
See also
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.
