Added to Favorites

Popular Searches

Definitions

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.## See also

## References

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.

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

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday November 20, 2007 at 09:26:46 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday November 20, 2007 at 09:26:46 PST (GMT -0800)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.