Wikipédia

Conjecture de Barnette

La conjecture de Barnette est un problème non résolu en théorie des graphes, concernant les cycles hamiltoniens dans les graphes. Elle affirme que tout graphe biparti polyédrique cubique possède un cycle hamiltonien. Elle porte le nom de David W. Barnette, professeur émérite à l'université de Californie à Davis.

Définitions modifier

Un graphe planaire est dit polyédrique si et seulement s'il est 3-sommet-connexe, c'est-à-dire s'il est encore connexe après la suppression de deux quelconques de ses sommets. Un graphe est biparti si ses sommets peuvent être colorés avec deux couleurs de telle sorte que chaque arête a des extrémités de couleurs différentes. Un graphe est cubique (ou 3-régulier) si chaque sommet est l'extrémité d'exactement trois arêtes. Enfin, un graphe est hamiltonien s'il existe un cycle qui passe par chacun de ses sommets exactement une fois. La conjecture de Barnette affirme que :

Tout graphe polyédrique bipartite cubique est hamiltonien.

Par le théorème de Steinitz (en), un graphe planaire représente les arêtes et les sommets d'un polyèdre convexe si et seulement s'il est polyédrique. Un polyèdre tridimensionnel représente un graphe cubique si et seulement si c'est un polyèdre simple ; de plus, un graphe planaire est biparti si et seulement si, dans un plongement planaire du graphe, les cycles des faces ont tous une longueur paire. Par conséquent, la conjecture de Barnette peut aussi être énoncée sous la forme équivalente :

Si un polyèdre convexe simple en trois dimensions a un nombre pair d'arêtes sur chacune de ses faces, alors le graphe du polyèdre a un cycle hamiltonien.

Historique modifier

P. G. Tait[1] a conjecturé en 1884 que tout graphe polyédrique cubique est hamiltonien ; cette conjecture est connue sous le nom de conjecture de Tait. Elle a été réfutée par W. T. Tutte en 1946[2] ; celui-ci a construit un contre-exemple avec 46 sommets ; d'autres chercheurs ont ensuite trouvé des contre-exemples plus petits. Cependant, aucun de ces contre-exemples connus n'est biparti. Tutte lui-même a conjecturé que tout graphe biparti cubique 3-connexe est hamiltonien, mais la découverte d'un contre-exemple, le graphe de Horton, a montré que cette hypothèse était fausse. David W. Barnette a proposé en 1969[3] une combinaison faible des conjectures de Tait et de Tutte, qui affirme que tout polyèdre cubique biparti est hamiltonien, ou, de manière équivalente, que tout contre-exemple à la conjecture de Tait est non biparti.

Formulations équivalentes modifier

Kelmans (1994)[4] a montré que la conjecture de Barnette est équivalente à un énoncé apparemment plus fort, à savoir que pour toute paire d'arêtes   et   sur une même face d'un polyèdre cubique biparti, il existe un cycle hamiltonien qui contient   mais ne contient pas  . Si cette propriété est vraie, alors tout polyèdre cubique biparti contient un cycle hamiltonien : il suffit de choisir   et   arbitrairement. Dans l'autre sens, Kelmans a montré qu'un contre-exemple pouvait être transformé en un contre-exemple à la conjecture originale de Barnette.

La conjecture de Barnette est aussi équivalente à l'énoncé selon lequel les sommets du dual d'un graphe polyédrique biparti cubique peuvent être partitionnés en deux sous-ensembles dont les sous-graphes induits sont des arbres. La coupe induite par une telle partition dans le graphe dual correspond à un cycle hamiltonien dans le graphe primal[5].

Résultats partiels modifier

Des calculs informatiques ont montré qu'il n'y a pas de contre-exemple à la conjecture de Barnette avec moins de 86 sommets[6],[7].

Si la conjecture de Barnette s'avère fausse, alors on peut montrer qu'il est NP-complet de tester si un polyèdre cubique biparti est hamiltonien. Si un graphe planaire est biparti et cubique mais seulement de connectivité 2, alors il peut être non hamiltonien, et il est NP-complet de tester l'hamiltonicité pour ces graphes[8]. Un autre résultat a été obtenu par Alt et al. 2016 : si les sommets du graphe dual peuvent être coloré en trois couleurs disons bleu, rouge et vert de telle sorte que chaque cycle bicoloré rouge-vert contienne un sommet de degré 4, alors le graphe primal est hamiltonien.

Problèmes connexes modifier

Une conjecture connexe de Barnette, prouvée depuis, affirme que :

tout graphe polyédrique cubique dans lequel toutes les faces ont six arêtes ou moins est hamiltonien.

Des calculs par ordinateur publiés en 2000 ont montré que, si un contre-exemple à cette conjecture existe, il devrait avoir plus de 177 sommets[9]. Mais en fait, la conjecture a depuis été prouvée par Kardoš en 2020[10].

L'intersection de ces deux conjectures est que

tout graphe polyédrique cubique biparti dans lequel toutes les faces ont quatre ou six arêtes est hamiltonien. Cela a été prouvé par Goodey en1975[11].

Références modifier

  1. ↑ Tait (1884).
  2. ↑ Tutte (1946).
  3. ↑ Barnette (1969).
  4. ↑ Kelmans (1994).
  5. ↑ Florek (2010).
  6. ↑ Holton, Manvel et McKay (1985).
  7. ↑ Hertel (2005).
  8. ↑ Akiyama, Nishizeki et Saito 1980.
  9. ↑ Aldred et al. (2000).
  10. ↑ Kardoš (2020).
  11. ↑ Goodey (1975).

Bibliographie modifier

Liens externes modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Conjecture_de_Barnette&oldid=193186489 ».