right|frame| 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'est-à-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 K7 (et par conséquent K5 et K6), le graphe de Petersen (et par conséquent le graphe biparti complet K3,3, qui en est un mineur), les snarks de Blanuša. et toutes les échelles de Möbius sont toroïdaux. Plus généralement, tout graphe de nombre de croisement é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..
Propriétés Tout graphe toroïdal est de nombre chromatique inférieur ou égal à sept. ; le graphe complet K7 est un exemple où ce nombre vaut 7 exactement. ; tout graphe toroïdal sans triangle a un nombre chromatique inférieur ou égal à quatre..
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 2019, on sait seulement qu'il comporte plus de 17 000 graphesEn 2018, une recherche systématique a obtenu obstructions, et un argument heuristique montre qu’il n’y en aurait au plus qu’une ou deux autres ; voir ..
Aspects algorithmiques
Les graphes toroïdaux peuvent être reconnus en temps polynomial (par contre déterminer le genre d'un graphe est un problème NP-complet).
Notes
Voir aussi Graphe planaire Théorème de Robertson-Seymour
Références
.
.
. . . . . . .
Toroïdal