PROFILPELAJAR.COM

	Graphe de Markström
	; Le graphe de Markström est sans cycle de longueur 4 ou 8, mais possède un cycle de longueur 16
Nombre de sommets	24
Nombre d'arêtes	32
Rayon	5
Diamètre	6
Maille	3
Automorphismes	3
Propriétés	Graphe cubique, planaire
	modifier

En théorie des graphes, la conjecture d' Erdős-Gyárfás, formulée en 1995 par les mathématiciens Paul Erdős et András Gyárfás^[1], est la suivante :

Conjecture d'Erdős-Gyárfás — Tout graphe de degré au moins 3 contient un cycle simple dont la longueur est une puissance de deux

Erdős a offert un prix de 100 $ pour la preuve de la conjecture, ou 50 $ pour un contre-exemple ; c'est l'une des nombreuses conjectures d'Erdős.

Discussion

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 $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 $|S|=O(n^{0.99})$ , tel que tout graphe à $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].

Notes et références

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

↑ Conjecture reprise dans (en) Paul Erdős, « Some old and new problems in various branches of combinatorics », Discrete Math., vol. 165-166,‎ 1997, p. 227-231 (zbMATH 0872.05020).
↑ Heckman et Krakovski (2013).
↑ Daniel et Shauger (2001).
↑ Shauger (1998).
↑ (en) Yuping Gao et Songling Shan, « Erdős-Gyárfás Conjecture for P8-free graphs », Arxiv preprnt,‎ septembre 2021 (arXiv 2109.01277).
↑ Verstraëte (2005).
↑ Sudakov et Verstraëte (2008).

Bibliographie

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