User:MWinter4/Heawood family

In graph theory the name Heawood family is used to refer to two related graph families that are closed under ΔY- and YΔ-transformations:

• the family of 20 graphs generated from the complete graph $K_{7}$.
• the family of 78 graphs generated from $K_{7}$ and $K_{3,3,1,1}$.

The members of either Heawood family are sometimes called Heawood graphs, though this has the potential for confusion with the Heawood graph. The Heawood graph is a however a members of both families. This is in analogy to the Petersen family, which too is named after a notable member – the Petersen graph.

The Heawood families play a major role in topological graph theory. No member of either family is 4-flat, and no members of the $K_{7}$-family is knotless.

No member of the Heawood family is 4-flat, and therefore neither linkless nor planar. All members have Colin de Verdière invariant $\mu =6$. It is conjectured that the family of Heawood graphs is the complete list of excluded minors for both the 4-flat graphs and the graphs with $\mu \leq 5$.

It is known that neither the Heawood family nor the $K_{7}$-family gives the complete list of excluded minors for the knotless graphs.

The $K_{7}$-family

The $K_{7}$-family plays an important role in the study of knotless graphs. All members of the family are excluded minors for the class of knotless graphs, but they are not a complete list.

The $\{K_{7},K_{3,3,1,1}\}$-family

Unsolved problem in mathematics:

Are the Heawood graphs the excluded minors of the 4-flat graphs and for $\mu \leq 5$?

(more unsolved problems in mathematics)

The Heawood family plays an important role in the study of 4-flat graphs. The Heawood graphs are the only excluded minors for the 4-flat graphs.

Background

The Heawood family naturally generalize the excluded minors for planar and linkless graphs. For all of those the list of excluded minors is closed under ΔY- and YΔ-transformations. The generators are:

• for planar, $K_{5}$ and $K_{3,3}$ (the Kuratowski graphs).
• for linkless, $K_{6}$ and $K_{3,3,1}$ (generate the Petersen family).
• (conjecturally) for 4-flat, $K_{7}$ and $K_{3,3,1,1}$ (generate the Heawood family).

For planar and linkless graphs it is actually sufficient to generate the excluded minors from only $K_{5}$ and $K_{6}$ respectively. For the Heawood family however both generators are necessary. The family generated by $K_{7}$ has 20 members and the family generated by $K_{3,3,1,1}$ has 58 members. The union of these disjoint families yields the Heawood family.