OFFSET
2,3
COMMENTS
Also, a(n) is the number of Hamiltonian planar triangulations with n+2 vertices. - Brendan McKay, Feb 20 2021
Yutsis graphs are connected cubic graphs which can be partitioned into two vertex-induced trees, which are necessarily of the same size. The cut separating both trees contains n+2 edges for a graph on 2n nodes, forming a Hamiltonian cycle in the planar dual if the graph is planar. These graphs are maximal in the number of nodes of the largest vertex-induced forests among the connected cubic graphs (floor((6n-2)/4) for a graph on 2n nodes). Whitney showed in 1931 that proving the 4-color theorem for a planar Yutsis graph implies the theorem for all planar graphs.
REFERENCES
F. Jaeger, On vertex induced-forests in cubic graphs, Proceedings 5th Southeastern Conference, Congressus Numerantium (1974) 501-512.
LINKS
L. H. Kauffman, Map Coloring and the Vector Cross Product, Journal of Combinatorial Theory, Series B, 48 (1990) 145-154.
D. Van Dyck, G. Brinkmann, V. Fack and B. D. McKay, To be or not to be Yutsis: algorithms for the decision problem, Computer Physics Communications 173 (2005) 61-70.
Dries Van Dyck and Veerle Fack, Yutsis project
FORMULA
MATHEMATICA
CROSSREFS
KEYWORD
nice,nonn,more
AUTHOR
Dries Van Dyck (VanDyck.Dries(AT)gmail.com), Mar 06 2006
EXTENSIONS
a(20) from Van Dyck et al. added by Andrey Zabolotskiy, Sep 10 2024
STATUS
approved