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

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

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

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 $e$ et $f$ sur une même face d'un polyèdre cubique biparti, il existe un cycle hamiltonien qui contient $e$ mais ne contient pas $f$ . Si cette propriété est vraie, alors tout polyèdre cubique biparti contient un cycle hamiltonien : il suffit de choisir $e$ et $f$ 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

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

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Barnette's conjecture » (voir la liste des auteurs).

↑ Tait (1884).
↑ Tutte (1946).
↑ Barnette (1969).
↑ Kelmans (1994).
↑ Florek (2010).
↑ Holton, Manvel et McKay (1985).
↑ Hertel (2005).
↑ Akiyama, Nishizeki et Saito 1980.
↑ Aldred et al. (2000).
↑ Kardoš (2020).
↑ Goodey (1975).

Bibliographie

Takanori Akiyama, Takao Nishizeki et Nobuji Saito, « NP-completeness of the Hamiltonian cycle problem for bipartite graphs », Journal of Information Processing, vol. 3, n^o 2,‎ 1980, p. 73–76 (MR 0596313, lire en ligne)
Helmut Alt, Michael S. Payne, Jens M. Schmidt et David R. Wood, « Thoughts on Barnette's conjecture », Australasian Journal of Combinatorics, vol. 64, n^o 2,‎ 2016, p. 354–365 (MR 3442496, lire en ligne)
R. E. L. Aldred, S. Bau, D. A. Holton et Brendan D. McKay, « Nonhamiltonian 3-connected cubic planar graphs », SIAM Journal on Discrete Mathematics, vol. 13, n^o 1,‎ 2000, p. 25–32 (DOI 10.1137/S0895480198348665 , MR 1737931)
David W. Barnette, « Conjecture 5 », dans W. T. Tutte (éditeur), Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, New York, Academic Press, 1969 (MR 0250896)
Tomas Feder et Carlos Subi, « On Barnette's conjecture », Electronic Colloquium on Computational Complexity,‎ 2006,, article n^o TR06-015 (lire en ligne)
Jan Florek, « On Barnette's conjecture », Discrete Mathematics, vol. 310, n^os 10-11,‎ 2010, p. 1531–1535 (DOI 10.1016/j.disc.2010.01.018, MR 2601261)
P. R. Goodey, « Hamiltonian circuits in polytopes with even sided faces », Israel Journal of Mathematics, vol. 22, n^o 1,‎ 1975, p. 52–56 (DOI 10.1007/BF02757273, MR 410565)
Alexander Hertel, « A survey & strengthening of Barnette’s conjecture », 2005
D. A. Holton, B. Manvel et B. D. McKay, « Hamiltonian cycles in cubic 3-connected bipartite planar graphs », Journal of Combinatorial Theory, Series B, vol. 38, n^o 3,‎ 1985, p. 279–297 (DOI 10.1016/0095-8956(85)90072-3, MR 0796604)
J. D. Horton, « On two-factors of bipartite regular graphs », Discrete Mathematics, vol. 41, n^o 1,‎ 1982, p. 35–41 (DOI 10.1016/0012-365X(82)90079-6, MR 0676860)
F. Kardoš, « A computer-assisted proof of the Barnette-Goodey Conjecture: not only fullerene graphs are hamiltonian », SIAM Journal on Discrete Mathematics, vol. 34, n^o 1,‎ 2020, p. 62–100 (DOI 10.1137/140984737, arXiv 1409.2440)
A. K. Kelmans, « Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles », dans A. K. Kelmans (éditeur), Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar 1972–1990, coll. « American Mathematical Society Translations, Series 2 » (n^o 158), 1994, p. 127–140
P. G. Tait, « Listing's Topologie », Philosophical Magazine, vol. 17,‎ 1884, p. 30–46; Reprinted in Scientific Papers, Vol. II, pp. 85–98
W. T. Tutte, « On Hamiltonian circuits », Journal of the London Mathematical Society, vol. 21, n^o 2,‎ 1946, p. 98–101 (DOI 10.1112/jlms/s1-21.2.98)
W. T. Tutte, « On the 2-factors of bicubic graphs », Discrete Mathematics, vol. 1, n^o 2,‎ 1971, p. 203–208 (DOI 10.1016/0012-365X(71)90027-6 , MR 0291010)