Bull graf - Bull graph - Wikipedia

Bull graf
Býčí graf
Vrcholy	5
Hrany	5
Poloměr	2
Průměr	3
Obvod	3
Automorfismy	2 (Z/2Z)
Chromatické číslo	3
Chromatický index	3
Vlastnosti	Rovinný Jednotková vzdálenost
Tabulka grafů a parametrů

V matematický pole teorie grafů, býčí graf je rovinný neorientovaný graf s 5 vrcholy a 5 hranami, ve formě trojúhelníku se dvěma disjunktními hranami přívěsku.^[1]

Má to chromatické číslo 3, chromatický index 3, poloměr 2, průměr 3 a obvod 3. Je to také a autokomplementární graf, a blokový graf, a dělený graf, an intervalový graf, a graf bez drápů, 1-graf spojený s vrcholem a 1-hranový graf.

Grafy bez býků

Graf neobsahuje býky, pokud nemá býka jako indukovaný podgraf. The grafy bez trojúhelníků jsou grafy bez býků, protože každý býk obsahuje trojúhelník. The silná dokonalá věta o grafu byl osvědčen pro bezbýlí grafy dlouho před jeho důkazem pro obecné grafy,^[2] a a polynomiální čas Algoritmus rozpoznávání dokonalých grafů bez Bull je znám.^[3]

Maria Chudnovsky a Shmuel Safra studovali grafy bez býků obecněji, což ukazuje, že každý takový graf musí mít buď velký klika nebo velký nezávislá sada (toto je Erdős – Hajnalův dohad drží pro býčí graf),^[4] a vývoj obecné teorie struktury pro tyto grafy.^[5]^[6]^[7]

Chromatický a charakteristický polynom

Tři grafy s a chromatický polynom rovná

{ displaystyle (x-2) (x-1) ^ {3} x}

.

The chromatický polynom býčího grafu je ${ displaystyle (x-2) (x-1) ^ {3} x}$ . Dva další grafy jsou chromaticky ekvivalentní býčímu grafu.

Své charakteristický polynom je ${ displaystyle -x (x ^ {2} -x-3) (x ^ {2} + x-1)}$ .

Své Tutteův polynom je ${ displaystyle x ^ {4} + x ^ {3} + x ^ {2} y}$ .

Reference

^ Weisstein, Eric W. „Bull Graph“. MathWorld.
^ Chvátal, V.; Sbihi, N. (1987), „Berge-free Berge graphs are perfect“, Grafy a kombinatorika, 3 (1): 127–139, doi:10.1007 / BF01788536.
^ Reed, B.; Sbihi, N. (1995), „Rozpoznávání dokonalých grafů bez býků“, Grafy a kombinatorika, 11 (2): 171–178, doi:10.1007 / BF01929485.
^ Chudnovský, M.; Safra, S. (2008), „Domněnka Erdős – Hajnal pro grafy bez býků“, Journal of Combinatorial Theory, Řada B, 98 (6): 1301–1310, doi:10.1016 / j.jctb.2008.02.005, archivovány z originál dne 25. 06. 2010, vyvoláno 2009-06-30.
^ Chudnovský, M. (2008), Struktura grafů bez býků. I. Cesty se třemi okraji se středy a protisměrem (PDF).
^ Chudnovský, M. (2008), Struktura grafů bez býků. II. Elementární trigrafy (PDF).
^ Chudnovský, M. (2008), Struktura grafů bez býků. III. Globální struktura (PDF).