Toroidal graph

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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[edit]

Any graph which can be embedded in a plane can also be embedded in a torus. A toroidal graph of genus 1 can be embedded in a torus but not in a plane. 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[edit]

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]

Obstructions[edit]

By the Robertson–Seymour theorem, there exists a finite set H of minimal non-toroidal graphs, such that a graph is toroidal if and only if it has no graph minor in H. That is, H forms the set of forbidden minors for the toroidal graphs. The complete set H is not known, but it has at least 17,523 graphs. Alternatively, there are at least 250,815 non-toroidal graphs that are minimal in the topological minor ordering. A graph is toroidal if and only if it has none of these graphs as a topological minor.[9]

See also[edit]

Notes[edit]

References[edit]