In graph theory, the Franklin graph is a 3- regular graph with 12 vertices and 18 edges [1] .
| Count Franklin | |
|---|---|
 | |
| Named after | |
| Tops | 12 |
| Rib | 18 |
| Radius | 3 |
| Diameter | 3 |
| Girth | four |
| Automorphisms | 48 ( Z / 2 Z × S 4 ) |
| Chromatic number | 2 |
| Chromatic Index | 3 |
| Rod | one |
| Properties | Cubic Hamiltonian Dicotyledonous No triangles Perfect Vertex-transitive |
The graph is named after , who disproved Hywood 's hypothesis about the number of colors required for coloring two-dimensional surfaces, divided into cells when nesting the graph [2] [3] . According to Hewood’s hypothesis, the maximum chromatic number of a card on a Klein bottle should be seven, but Franklin proved that for a given graph of six colors it is always sufficient. Count Franklin can be put in a Klein bottle so that it forms a card that requires six colors, which shows that in some cases six colors are enough. This embedding is a Petri dual embedding in the projective plane (the embedding is shown below).
The graph is Hamiltonian and has a chromatic number of 2, a chromatic index of 3, a radius of 3, a diameter of 3, and a girth of 4. It is also a vertex 3-connected and edge-3-connected perfect graph .
Algebraic properties
The automorphism group of the Franklin graph has order 48 and is isomorphic to Z / 2 Z × S 4 , the direct product of the cyclic group Z / 2 Z and the symmetric group S 4 . The group acts transitively on the vertices of the graph.
The characteristic polynomial of the graph of Franklin is
Gallery
The chromatic number of the graph of Franklin is 2.
The chromatic index of Count Franklin is 3.
An alternative drawing of Count Franklin.
Count Franklin, embedded in the projective plane as a truncated .
Notes
- ↑ Weisstein, Eric W. Franklin Graph (English) on Wolfram MathWorld .
- ↑ Weisstein, Eric W. Heawood conjecture (Eng.) On the Wolfram MathWorld website.
- ↑ Franklin, 1934 , p. 363-379.
Literature
- P. Franklin. A Six Color Problem // J. Math. Phys .. - 1934. - T. 13 . - p . 363-379 .