Conjecture d'Erdős-Gyárfás
Modèle:Infobox Graphe 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 : Modèle:Théorème 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-connexesModèle:Sfnp. La conjecture est également vérifiée pour les graphes planaires sans griffes Modèle:Sfnp, et pour les graphes qui évitent les grands graphes étoiles induits et qui satisfont à des contraintes supplémentaires sur leurs degrésModèle:Sfnp. La conjecture est aussi vraie pour les graphes « sans » 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[2].
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 , tel que tout graphe à sommets de degré moyen 10 ou plus contient un cycle dont la longueur figure dans S Modèle:Sfnp, 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 deuxModèle:Sfnp.
Notes et références
Modèle:Traduction/référence Modèle:Références
Bibliographie
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article
- Modèle:Article.
- Modèle:Article.
Liens externes
- 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 »
Articles connexes
- ↑ Conjecture reprise dans Modèle:Article.
- ↑ Modèle:Article.