Graphe toroïdal

Un graphe plongé sur le tore de telle façon que les arêtes ne se coupent pas.

En mathématiques, et plus précisément en théorie des graphes , un graphe G est toroïdal s'il peut être plongé sur le tore, c'et-à-dire que les sommets du graphe peuvent être placés sur le tore de telle façon que les arêtes ne se coupent pas. En général dire qu'un graphe est toroïdal sous-entend également qu'il n'est pas planaire.

Exemples

Le graphe de Heawood, le graphe complet K₇ (et par conséquent K₅ et K₆), le graphe de Petersen (et par conséquent le graphe biparti complet K_3,3, qui en est un mineur), les snarks de Blanuša^[1], et toutes les échelles de Möbius (en) sont toroïdaux. Plus généralement, tout graphe de nombre de croisement (en) égal à 1 est toroïdal. Certains graphes ayant un nombre de croisement supérieur sont également toroïdaux : ainsi, le graphe de Möbius-Kantor, de nombre de croisement 4, est toroïdal^[2].

Propriétés

Tout graphe toroïdal est de nombre chromatique inférieur ou égal à sept^[3] ; le graphe complet K₇ est un exemple où ce nombre vaut 7 exactement^[4] ; tout graphe toroïdal sans triangles a un nombre chromatique inférieur ou égal à quatre^[5].

Le théorème de Robertson-Seymour montre qu'on peut caractériser les graphes toroïdaux (ou planaires) par un ensemble fini de mineurs exclus (comme le théorème de Kuratowski le fait pour les graphes planaires), mais cet ensemble n'est pas encore déterminé ; en 2011, on sait seulement qu'il comporte plus de 16 000 graphes^[6].

Notes

Voir aussi

• Graphe planaire
• Théorème de Robertson-Seymour

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Toroidal graph » (voir la liste des auteurs)

• (en) Gary Chartrand et Ping Zhang, Chromatic graph theory, CRC Press, 2008 (ISBN 9781584888000) .
• (en) Toshiki Endo, « The pagenumber of toroidal graphs is at most seven », dans Discrete Mathematics, vol. 175, n^o 1–3, 1997, p. 87–96 [lien DOI] .
• (en) Steven J. Gortler, « Discrete one-forms on meshes and applications to 3D mesh parameterization », dans Computer Aided Geometric Design, vol. 23, n^o 2, 2006, p. 83–112 [lien DOI] .
• (en) P. J. Heawood, « Map colouring theorems », dans Quarterly J. Math. Oxford Ser., vol. 24, 1890, p. 322–339 .
• (en) W. Kocay, « Drawing graphs on the torus », dans Ars Combinatoria, vol. 59, 2001, p. 259–277 [texte intégral] .
• (en) Hudson V. Kronk, « A 4-color theorem for toroidal graphs », dans Proceedings of the American Mathematical Society, American Mathematical Society, vol. 34, n^o 1, 1972, p. 83–86 [lien DOI] .
• (en) Dragan Marušič, « The remarkable generalized Petersen graph G(8,3) », dans Math. Slovaca, vol. 50, 2000, p. 117–121 [texte intégral] .
• (en) Eugene Neufeld et Wendy Myrvold, Practical toroidality testing (dans Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms), 1997, 574–580 p. [lire en ligne] .
• (en) Alen Orbanić, « Blanuša double », dans Math. Commun., vol. 9, n^o 1, 2004, p. 91–103 .

• Portail de la géométrie