Snark (graphe)

Peter Guthrie Tait a initié l'étude des snarks en 1880, quand il a prouvé que démontrer le théorème des quatre couleurs revenait à démontrer que tout graphe cubique planaire pouvait avoir ses arêtes colorées avec trois couleurs. Ou dit autrement, qu'aucun snark n'est planaire[2].

Le premier snark connu était le graphe de Petersen, découvert en 1898. En 1946, le mathématicien croate Danilo Blanuša découvrit deux autres snarks, tous deux à 18 sommets, à présent appelés les snarks de Blanuša[3]. Le quatrième snark connu a été découvert deux ans plus tard par Bill Tutte, sous le pseudonyme de Blanche Descartes, et comportait 210 sommets[4] - [5]. En 1973, George Szekeres a découvert le cinquième snark connu, le snark de Szekeres[6]. En 1975, Rufus Isaacs a généralisé la méthode de Blanuša afin de construire deux familles infinies de snarks : les snarks fleurs et les BDS ou snarks de Blanuša-Descartes-Szekeres, une famille qui comprend les deux snarks de Blanuša, le snark de Descartes et le snark de Szekeres[7]. Isaacs découvrit aussi un snark à 30 sommets qui n'appartient pas à la famille BDS et qui n'est pas un snark fleur : le snark double étoile.

Écrivant dans The Electronic Journal of Combinatorics, Miroslav Chladný affirme que « En étudiant les nombreux problèmes importants et difficiles de la théorie des graphes (comme la conjecture du double recouvrement et la conjecture du 5-flux, on tombe sur une sorte intéressante de graphes quelque peu mystérieuse appelés snarks. En dépit de leur simple définition … et après plus d'un siècle d'investigations, leurs propriétés et leur structure restent largement inconnues[8]. »

Tous les snarks sont non-hamiltoniens, et plusieurs snarks connus sont hypohamiltoniens : en supprimant n'importe quel sommet, le graphe devient hamiltonien. Un snark hypohamiltonien est forcément bicritique : en supprimant n'importe quelle paire de sommets, les arêtes du graphes peuvent être colorées avec 3 couleurs[9] - [10].

On a pu démontrer que le nombre de snarks ayant un nombre pair donné de sommets est minoré par une fonction exponentielle de ce nombre de sommets[11] (comme les snarks sont des graphes cubiques, ils ont forcément un nombre de sommets pair). La suite A130315 de l'OEIS donne le nombre de snarks non triviaux à ${\displaystyle 2n}$ sommets pour les petites valeurs de ${\displaystyle n}$ : 0, 0, 0, 0, 1, 0, 0, 0, 2, 6, 20, 38, 280, 2900, 28399, 293059, 3833587, 60167732.

Un double revêtement du graphe de Petersen à l'aide de cycles.

La conjecture du double revêtement (en) affirme que dans tout graphe sans isthme, on peut trouver un ensemble de cycles passant deux fois par chaque arête. Une formulation équivalente est que le graphe peut être plongé (en) dans une surface de telle sorte que toutes les faces du plongement soient des cycles simples.

Les snarks forment le cas difficile dans cette conjecture : si elle est vraie pour les snarks, elle le sera pour tous les graphes[12].

En rapport avec ce problème, Branko Grünbaum a émis la conjecture qu'il était impossible de plonger un graphe sur une surface de sorte que toutes les faces soient des cycles simples et que deux faces quelconques soit soient disjointes soit partagent une seule arête commune. Cette conjecture s'est révélée fausse, Martin Kochol ayant trouvé un contre-exemple[13] - [14] - [15].

W. T. Tutte a émis la conjecture que tout snark a le graphe de Petersen comme mineur. En d'autres termes, il a émis l'hypothèse que l'on pouvait obtenir le plus petit snark, le graphe de Petersen, à partir de n'importe quel autre snark en contractant certaines arêtes et en supprimant des sommets isolés ou des arêtes.

Une hypothèse équivalente est que tout snark peut être formé à partir du graphe de Petersen en subdivisant certaines de ses arêtes par homéomorphisme.

En 1999, Neil Robertson, Daniel Sanders, Paul Seymour et Robin Thomas ont annoncé une démonstration de la conjecture de Tutte[16]. Sarah-Marie Belcastro fait néanmoins remarquer qu'en 2012, leur démonstration reste en grande partie non publiée.

Tutte a également émis une conjecture généralisant le théorème du snark à des graphes arbitraires : tout graphe sans isthme et sans graphe de Petersen comme mineur un flux nulle part nul de type 4 (en). Cela signifie que les arêtes du graphe peuvent se voir affecter une orientation et un nombre égal à 1, 2 ou 3, de façon que la somme des nombres entrants moins la somme des nombres sortants soit divisible par 4 quel que soit le sommet. Comme Tutte l'a montré, pour les graphes cubiques une telle affectation existe si et seulement si les arêtes peuvent être colorées avec 3 couleurs, donc la conjecture découle du théorème du snark dans le cas des graphes cubiques. Néanmoins, la conjecture reste ouverte pour les autres graphes[17].

• Graphe de Petersen (10 sommets, découvert en 1898)
• Graphe de Tietze (12 sommets, mais avec une maille de 3, en général pas considéré comme un snark)
• Premier snark de Blanuša et second snark de Blanuša (18 sommets ; découvert en 1946)
• Snark de Descartes (famille finie de graphes à 210 sommets ; découvert par Bill Tutte en 1948)
• Snark double étoile (30 sommets)
• Premier snark de Celmins-Swart, second snark de Celmins-Swart
• Premier snark de Loupekine, second snark de Loupekine
• Snark de Szekeres (50 sommets ; découvert en 1973)
• Snark de Watkins (50 sommets ; découvert en 1989)
• Snark fleur (famille infinie à 20, 28, 36, 44... sommets, découverte en 1975)
• Snark de Goldberg (autre famille infinie)

En 2012, Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund et Klas Markström ont généré tous les snarks jusqu'à 36 sommets grâce à une recherche par ordinateur[18].