From Surf Wiki (app.surf) — the open knowledge base

Franklin graph

Graph often embedded in the Klein bottle

Field	Value
name	Franklin Graph
image	[[Image:Franklin graph hamiltonian.svg	220px]]
image_caption	The Franklin Graph
namesake	Philip Franklin
vertices	12
edges	18
automorphisms	48 (Z/2Z×S4)
girth	4
radius	3
diameter	3
genus	1
chromatic_number	2
chromatic_index	3
properties	Cubic
Hamiltonian
Bipartite
Triangle-free
Perfect
Vertex-transitive

Hamiltonian Bipartite Triangle-free Perfect Vertex-transitive In the mathematical field of graph theory, the Franklin graph is a 3-regular graph with 12 vertices and 18 edges.

The Franklin graph is named after Philip Franklin, who disproved the Heawood conjecture on the number of colors needed when a two-dimensional surface is partitioned into cells by a graph embedding. The Heawood conjecture implied that the maximum chromatic number of a map on the Klein bottle should be seven, but Franklin proved that in this case six colors always suffice. (The Klein bottle is the only surface for which the Heawood conjecture fails.) The Franklin graph can be embedded in the Klein bottle so that it forms a map requiring six colors, showing that six colors are sometimes necessary in this case. This embedding is the Petrie dual of its embedding in the projective plane shown below.

It is Hamiltonian and has chromatic number 2, chromatic index 3, radius 3, diameter 3 and girth 4. It is also a 3-vertex-connected and 3-edge-connected perfect graph.

Algebraic properties

The automorphism group of the Franklin graph is of order 48 and is isomorphic to Z/2Z×S4, the direct product of the cyclic group Z/2Z and the symmetric group S4. It acts transitively on the vertices of the graph, making it vertex-transitive.

The characteristic polynomial of the Franklin graph is :(x-3) (x-1)^3 (x+1)^3 (x+3) (x^2-3)^2.\

Gallery

Image: Franklin graph 2COL.svg |The chromatic number of the Franklin graph is 2. Image: Franklin graph 3color edge.svg|The chromatic index of the Franklin graph is 3. Image:franklin_graph.svg|Alternative drawing of the Franklin graph. Image:Franklin graph in projective plane.svg|The Franklin graph embedded in the projective plane as the truncated hemi-octahedron. File:6-crossed-prism graph.svg|Franklin graph as a 6-sided crossed prism graph; it is 1-planar.

References

Franklin, P. "A Six Color Problem." J. Math. Phys. 13, 363-379, 1934. {{doi. 10.1002/sapm1934131363

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

individual-graphs regular-graphs

Want to explore this topic further?

Ask Mako anything about Franklin graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report