Tóruszra rajzolható gráf

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.

Egy 14 csúcsú 3-reguláris gráf tóruszba ágyazása

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 K₇ teljes gráf (és így a K₅ és a K₆ is), a Petersen-gráf (és így a K_3,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 K₇ 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 17 523 gráfot tartalmaz. Más megközelítésben, legalább 250 815 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

• Ez a szócikk részben vagy egészben a Toroidal graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Chartrand, Gary & Zhang, Ping (2008), Chromatic graph theory, CRC Press, ISBN 978-1-58488-800-0.
• Endo, Toshiki (1997), "The pagenumber of toroidal graphs is at most seven", Discrete Mathematics 175 (1–3): 87–96, DOI 10.1016/S0012-365X(96)00144-6.
• Gortler, Steven J.; Gotsman, Craig & Thurston, Dylan (2006), "Discrete one-forms on meshes and applications to 3D mesh parameterization", Computer Aided Geometric Design 23 (2): 83–112, DOI 10.1016/j.cagd.2005.05.002.
• Heawood, P. J. (1890), "Map colouring theorems", Quarterly J. Math. Oxford Ser. 24: 322–339.
• Kocay, W.; Neilson, D. & Szypowski, R. (2001), "Drawing graphs on the torus", Ars Combinatoria 59: 259–277, <http://bkocay.cs.umanitoba.ca/g&g/articles/Torus.pdf>. Hozzáférés ideje: 2006-10-28 Archiválva 2004. december 24-i dátummal a Wayback Machine-ben.
• Kronk, Hudson V. & White, Arthur T. (1972), "A 4-color theorem for toroidal graphs", Proceedings of the American Mathematical Society (American Mathematical Society) 34 (1): 83–86, DOI 10.2307/2037902.
• Marušič, Dragan & Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Math. Slovaca 50: 117–121, <http://www.mat.savba.sk/maslo/maslo.mat.savba.sk/Full/50/2/MAR-PIS.ps>.
• Myrvold, Wendy & Woodcock, Jennifer (2018), "A large set of torus obstructions and how they were discovered", Electronic Journal of Combinatorics 25 (1): P1.16
• Neufeld, Eugene & Myrvold, Wendy (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574–580, <http://portal.acm.org/citation.cfm?id=314392>.
• Orbanić, Alen; Pisanski, Tomaž & Randić, Milan et al. (2004), "Blanuša double", Math. Commun. 9 (1): 91–103.