Conjecture d'Erdős-Gyárfás

La conjecture d'Erdős-Gyárfás est vraie dans le cas particulier des graphes planaires cubiques 3-connexes[2]. La conjecture est également vérifiée pour les graphes planaires sans griffes [3], et pour les graphes qui évitent les grands graphes étoiles induits et qui satisfont à des contraintes supplémentaires sur leurs degrés[4]. La conjecture est aussi vraie pour les graphes « sans ${\displaystyle P_{8}}$ » qui sont les graphes qui n'ont pas de sous-graphe induit qui est une chaîne de longueur 8 ; ce résultat est annoncé en septembre 2021[5].

Un contre-exemple à la conjecture, s'il existe, est un graphe de degré minimum 3 ne possédant pas de cycle dont la longueur est une de puissance de 2. Une recherche par ordinateur de Gordon Royle et Klas Markström montre qu'un contre-exemple doit avoir au moins 17 sommets, et qu'un contre-exemple cubique doit avoir au moins 30 sommets. Les recherches de Markström ont fourni quatre graphes sur 24 sommets dans lesquels les seuls cycles de longueur une puissance de deux ont 16 sommets. L'un de ces quatre graphes est planaire.

Des résultats plus faibles reliant le degré d'un graphe à des ensembles de longueurs inévitables de cycles ont été démontrés : il existe un ensemble S de longueurs, de taille ${\displaystyle |S|=O(n^{0.99})}$, tel que tout graphe à ${\displaystyle n}$ sommets de degré moyen 10 ou plus contient un cycle dont la longueur figure dans S [6], et tout graphe dont le degré moyen est exponentiel en le logarithme itéré de n contient nécessairement un cycle dont la longueur est une puissance de deux[7].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Gyárfás conjecture » (voir la liste des auteurs).

• (en) Mushtaq Ahmad Shah, Mridula Purohit et M. H. Gulzar, « a survey and strengthening of Erdős–Gyárfás conjecture », Advances in Mathematics: Scientific Journal, vol. 5, n^o 2,‎ 2016, p. 117-121 (ISSN 1857-8438).
• Dale Daniel et Stephen E. Shauger, « A result on the Erdős–Gyárfás conjecture in planar graphs », Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing,‎ 2001, p. 129–139.
• Christopher Carl Heckman et Roi Krakovski, « Erdös-Gyárfás conjecture for cubic planar graphs », Electronic Journal of Combinatorics, vol. 20, n^o 2,‎ 2013, article n^o P7 (lire en ligne).
• (en) Mohammad Hossein Ghaffari et Zohreh Mostaghim, « Erdős–Gyárfás conjecture for some families of Cayley graphs », Aequationes mathematicae, vol. 92,‎ 2018, p. 1-6 (DOI 10.1007/s00010-017-0518-3).
• Klas Markström, « Extremal graphs for some problems on cycles in graphs », Congr. Numerantium, vol. 171,‎ 2004, p. 179–192 (lire en ligne).
• Stephen E. Shauger, « Results on the Erdős–Gyárfás conjecture in K_1,m-free graphs », Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing,‎ 1998, p. 61–65
• Benny Sudakov et Jacques Verstraëte, « Cycle lengths in sparse graphs », Combinatorica, vol. 28, n^o 3,‎ 2008, p. 357–372 (DOI 10.1007/s00493-008-2300-6, arXiv 0707.2117).
• Jacques Verstraëte, « Unavoidable cycle lengths in graphs », Journal of Graph Theory, vol. 49, n^o 2,‎ 2005, p. 151–167 (DOI 10.1002/jgt.20072).

• Geoffrey Exoo, « Graphs Without Cycles of Specified Lengths »
• Douglas B. West, « Erdős Gyárfás Conjecture on 2-power Cycle Lengths »
• Douglas B. West, « Open Problems - Graph Theory and Combinatorics »

• Liste de conjectures d'Erdős
• Liste de sujets nommés d'après Paul Erdős (en)