Snark (graphe)

En théorie des graphes, une branche des mathématiques, un snark est un graphe cubique connexe, sans isthme et d'indice chromatique égal à 4. En d'autres termes, c'est un graphe dans lequel chaque sommet a trois voisins, et dont les arêtes ne peuvent pas être colorées avec seulement 3 couleurs sans que deux arêtes de même couleur ne se rencontrent en un même sommet (d'après le théorème de Vizing, l'indice chromatique d'un graphe cubique est 3 ou 4). Pour éviter les cas triviaux, on exige souvent de plus que les snarks aient une maille d'au moins 5. Les snarks ont été nommés ainsi par le mathématicien américain Martin Gardner en 1976, d'après l'objet mystérieux et insaisissable du poème La Chasse au Snark de Lewis Carroll. 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. 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. 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. En 1973, George Szekeres a découvert le cinquième snark connu, le snark de Szekeres. 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. 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 Tous les snarks sont non-hamiltoniens, et plusieurs snarks connus sont hypohamiltoniens : en supprimant n'importe quel sommet, le graphe devient hamiltonien.