Toroidal graph

File:Toroidal graph sample.gif

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 K₇ (and hence K₅ and K₆), the Petersen graph (and hence the complete bipartite graph K_3,3, since the Petersen graph contains a subdivision of it), one of the Blanuša snarks, 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.

Properties

Any toroidal graph has chromatic number at most 7. The complete graph K₇ provides an example of toroidal graph with chromatic number 7.

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

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. Furthermore, the analogue of Tutte's spring theorem applies in this case. Toroidal graphs also have book embeddings with at most 7 pages.

See also

• Planar graph
• Topological graph theory
• Császár polyhedron

References

• .
• .
• .
• .
• .
• .
• .
• .
• .