Conjecture d'Erdős-Burr
# 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), concerne la croissance du nombre de Ramsey d'un graphe non orienté de degré de dégénérescence donné, en fonction de son nombre de sommets. Elle a été démontrée par Choongbum Lee en $2015^,.$

Il découle du théorème de Ramsey qu'il existe un plus petit entier r(G), 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.

Un graphe est dit p-dégénéré si tout sous-graphe contient un sommet de degré inférieur ou égal à p.

La conjecture est :

    pour tout entier p, il existe une constante $c_p$ telle que tout graphe p-dégénéré à n sommets ait son nombre de Ramsey majoré par $c_p$ n.

Avant d'être démontrée, elle 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 $K_{p}$ ;
* pour les graphes subdivisés.
