Conjecture de Erdős-Burr

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 contienne une copie monochromatique de G.

En 1973, Erdős et Burr ont proposé la conjecture suivante:

Pour tout entier p, il existe une constante cp telle que tout graphe G ayant n sommets et dont tous les sous-graphes ont un degré minimum au moins p ait son nombre de Ramsey borné par r(G)\leq c_p n.

Cette conjecture a été vérifiée dans certains cas particuliers:

  • pour les graphes de degré maximal borné;
  • pour les graphes p-arrangeables et, en particulier, les graphes planaires et les graphes sans subdivisions de Kp;
  • pour les graphes subdivisés.

Références

  • 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¨os 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.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Conjecture d%27Erd%C5%91s-Burr ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Conjecture de Erdős-Burr de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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

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

  • 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

  • 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

  • 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

Share the article and excerpts

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