A matematika, azon belül a gráfelmélet területén egy tóruszra rajzolható gráf vagy tóruszba ágyazható gráf (toroidal graph) olyan gráf, melynek létezik tóruszba ágyazása. Más szavakkal a gráf csúcsai elhelyezhetők úgy egy tóruszfelületen, hogy az élei ne metsszék egymást.
Példák Bármely síkbarajzolható gráf tóruszra is rajzolható. Ha a gráf génusza 1, a gráf tóruszra rajzolható, de síkba nem. A Heawood-gráf, a K7 teljes gráf (és így a K5 és a K6 is), a Petersen-gráf (és így a K3,3 teljes páros gráf, mivel a Petersen-gráf tartalmazza annak felosztását), a Blanuša-snarkok egyike, és az összes Möbius-létra is tóruszra rajzolható. Általánosabban, az 1 metszési számú gráfok mind tóruszba ágyazhatók. Néhány magasabb metszési számmal rendelkező gráf is tóruszba ágyazható: például a Möbius–Kantor-gráf, metszési száma 4, mégis tóruszra lehet rajzolni.
Tulajdonságok Tetszőleges tóruszra rajzolható gráf kromatikus száma legfeljebb 7. A K7 teljes gráf jó példa olyan tóruszra rajzolható gráfra, aminek kromatikus száma ténylegesen el is éri a hetet.
A háromszögmentes tóruszra rajzolható gráfok kromatikus száma legfeljebb 4.
A Fáry-tétellel analóg eredmény alapján bármely tóruszra rajzolható gráf lerajzolható egyenes vonalakkal egy periodikus peremfeltételekkel rendelkező téglalapban. Ebben az esetben a Tutte-féle rugók tételének analógiája is működik. A tóruszra rajzolható gráfoknak létezik olyan könyvbe ágyazásuk, melyek legfeljebb 7 lapból állnak.
Obstrukciók A Robertson–Seymour-tétel alapján létezik minimális, nem tóruszra rajzolható gráfok olyan véges H halmaza, hogy bármely gráf pontosan akkor tóruszra rajzolható, ha egyetlen gráfminora sem szerepel H-ban. Más szavakkal H megadja a tóruszra rajzolható gráfok tiltott minor-alapú karakterizációját. A teljes H halmaz nem ismert, de legalább gráfot tartalmaz. Más megközelítésben, legalább olyan, nem tóruszra rajzolható gráf létezik, ami a topologikus minor-rendezés szerint minimális. Egy gráf pontosan akkor tóruszra rajzolható, ha ezek közül egyiket se tartalmazza topologikus minorként.
Kapcsolódó szócikkek Síkba rajzolható gráf Topologikus gráfelmélet Császár-féle test
Fordítás
Jegyzetek
. . . . . . .
. .
Kategória:Gráfcsaládok Kategória:Topologikus gráfelmélet