Tóruszra rajzolható gráf

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

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,[1] é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.[2]

Tulajdonságok

Tetszőleges tóruszra rajzolható gráf kromatikus száma legfeljebb 7.[3] 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.[4]

A háromszögmentes tóruszra rajzolható gráfok kromatikus száma legfeljebb 4.[5]

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.[6] Ebben az esetben a Tutte-féle rugók tételének analógiája is működik.[7] A tóruszra rajzolható gráfoknak létezik olyan könyvbe ágyazásuk, melyek legfeljebb 7 lapból állnak.[8]

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.[9]

Kapcsolódó szócikkek

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>[halott link].
  • 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.