Erdős–Burr conjecture

From Wikipedia, the free encyclopedia

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.

[edit] See also

Erdős conjecture

[edit] 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.