Golombův graf - Golomb graph

Golombův graf
Pojmenoval podle	Solomon W. Golomb
Vrcholy	10
Hrany	18
Chromatické číslo	4
Vlastnosti	mnohostěnný jednotková vzdálenost
Tabulka grafů a parametrů

v teorie grafů, Golombův graf je polyedrický graf s 10 vrcholy a 18 hrany. Je pojmenován po Solomon W. Golomb, který ji postavil (srovinný vkládání) jako a graf jednotkové vzdálenosti který vyžaduje čtyři barvy v jakékoli zbarvení grafu. Tak, jako jednodušší Moser vřeteno, poskytuje dolní mez pro Hadwiger – Nelsonův problém: zbarvení bodů Euklidovské letadlo takže každá jednotka úsečka má různě zbarvené koncové body, vyžaduje alespoň čtyři barvy.^[1]

Konstrukce

4-zbarvení Golombova grafu, nakreslené jako graf jednotkové vzdálenosti

Metoda konstrukce grafu Golomb jako grafu jednotkové vzdálenosti nakreslením vnějšího pravidelného polygonu připojeného k vnitřnímu zkroucenému polygonu nebo hvězdicovému polygonu byla také použita pro reprezentaci jednotkových vzdáleností Petersenův graf a ze dne zobecněné Petersenovy grafy.^[2] Stejně jako u Moserova vřetena mohou být souřadnice jednotkové vzdálenosti vložené do Golombova grafu znázorněny v kvadratické pole ${ displaystyle mathbb {Q} [{ sqrt {33}}]}$.^[3]

Frakční zbarvení

The zlomkové chromatické číslo grafu Golomb je 10/3. Skutečnost, že toto číslo je alespoň tak velké, vyplývá ze skutečnosti, že graf má 10 vrcholů, z nichž nejvýše tři mohou být v libovolné nezávislé množině. Skutečnost, že toto číslo je nanejvýš tak velké, vyplývá ze skutečnosti, že lze najít 10 nezávislých množin tří vrcholů, takže každý vrchol je přesně ve třech z těchto množin. Toto zlomkové chromatické číslo je menší než číslo 7/2 pro Moserovo vřeteno a menší než zlomkové chromatické číslo grafu jednotkové vzdálenosti letadla, který je ohraničen mezi 3,6190 a 4,3599.^[4]

Reference

externí odkazy

• Weisstein, Eric W. „Golombův graf“. MathWorld.