Toroidal graph

A cubic graph with 14 vertices embedded on a torus

In mathematics, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.

Examples

The Heawood graph, the complete graph K7 (and hence K5 and K6), the Petersen graph (and hence the complete bipartite graph K3,3, since the Petersen graph contains a subdivision of it), one of the Blanuša snarks,[1] and all Möbius ladders are toroidal. More generally, any graph with crossing number 1 is toroidal. Some graphs with greater crossing numbers are also toroidal: the Möbius–Kantor graph, for example, has crossing number 4 and is toroidal.[2]

Properties

Any toroidal graph has chromatic number at most 7.[3] The complete graph K7 provides an example of toroidal graph with chromatic number 7.[4]

Any triangle-free toroidal graph has chromatic number at most 4.[5]

By a result analogous to Fáry's theorem, any toroidal graph may be drawn with straight edges in a rectangle with periodic boundary conditions.[6] Furthermore, the analogue of Tutte's spring theorem applies in this case.[7] Toroidal graphs also have book embeddings with at most 7 pages.[8]

See also

Notes

References

This article is issued from Wikipedia - version of the Monday, February 01, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.