Erdős–Burr conjecture

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.

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Conjecture d'Erdős-Burr — En théorie des graphes, la conjecture d Erdős Burr, proposée en 1973 par Paul Erdős et Stefan Burr (en) et toujours non résolue, concerne la croissance du nombre de Ramsey d un graphe non orienté de degré de dégénérescence donné, en fonction …   Wikipédia en Français

  • Conjecture de Erdős-Burr — Conjecture d Erdős Burr Soit G un graphe simple. Il découle du théorème de Ramsey qu il existe un entier r(G) minimal, le nombre de Ramsey de G, tel que tout graphe complet d au moins r(G) sommets dont les arêtes sont coloriées en rouge et bleu… …   Wikipédia en Français

  • Erdős conjecture — The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects.Some of these are the following: * The Cameron–Erdős conjecture on sum free sets of integers, solved by… …   Wikipedia

  • Erdos — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

  • Erdös — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

  • List of things named after Paul Erdős — The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… …   Wikipedia

  • Paul Erdős — Paul Erdős, 1992 Paul Erdős (Erdős Pál /ˈɛrdøːʃ paːl …   Wikipédia en Français

  • Paul Erdos — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

  • Paul Erdös — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

  • Pál Erdős — Paul Erdős Paul Erdős, 1992 Paul Erdős (Erdős Pál …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”