Hrabě z Franklin

V teorii grafů je Franklinův graf  3- regulární graf s 12 vrcholy a 18 hranami [1] .

Graf je pojmenován po Philipu Franklinovi , který vyvrátil Heawoodovu domněnku o počtu barev potřebných k obarvení dvourozměrných povrchů rozdělených do buněk, když je graf vložen [2] [3] . Podle Heawoodova dohadu by maximální chromatické číslo mapy na Kleinově láhvi mělo být sedm, ale Franklin dokázal, že šest barev je pro daný graf vždy dostačujících. Franklinův graf lze vložit do Kleinovy ​​láhve tak, že tvoří kartu vyžadující šest barev, což ukazuje, že v některých případech stačí šest barev. Toto vložení je Petriho duálem vložení do projektivní roviny (vložení znázorněno níže).

Graf je hamiltonovský a má chromatické číslo 2, chromatický index 3, poloměr 3, průměr 3 a obvod 4. Je to také dokonalý graf s 3 vrcholy a 3 hranami .

Algebraické vlastnosti

Skupina automorfismu Franklinova grafu má řád 48 a je izomorfní k Z /2 Z × S 4 , přímému součinu cyklické grupy Z /2 Z a symetrické grupy S 4 . Skupina působí tranzitivně na vrcholy grafu.

Charakteristickým polynomem Franklinova grafu je

Galerie

• Chromatické číslo hraběte Franklina je 2.

• Chromatický index hraběte Franklina je 3.

• Alternativní kresba hraběte Franklina.

• Franklinův graf vložený do projektivní roviny jako zkrácený semi-oktaedr .

Poznámky

1. ↑ Weisstein, Eric W. Franklin Graph  na webu Wolfram MathWorld .
2. ↑ Weisstein, Eric W. Heawood dohad  na webu Wolfram MathWorld .
3. ↑ Franklin, 1934 , str. 363-379.

Literatura

• P. Franklin. Šestibarevný problém // J. Math. Fyz.. - 1934. - T. 13 . - S. 363-379 .