Býčí hlava | |
---|---|
Vrcholy | 5 |
žebra | 5 |
Poloměr | 2 |
Průměr | 3 |
obvod | 3 |
Automorfismy | 2 ( Z / 2 Z ) |
Chromatické číslo | 3 |
Chromatický index | 3 |
Vlastnosti |
Rovinný graf jednotkový graf vzdálenosti |
Býčí hlava je rovinný neorientovaný graf s 5 vrcholy a 5 hranami ve tvaru trojúhelníku se dvěma nesouvislými převislými hranami [1] .
Barevné číslo grafu je 3, chromatický index je 3, poloměr je 2, průměr je 3 a obvod je 3. Graf je blokový , dělený , bezdrápý , vertex -1-connected a 1- edge -připojeno .
Graf je bez býčích hlav, pokud hlava není obsažena jako vygenerovaný podgraf . Grafy bez trojúhelníků neobsahují býčí hlavy, protože každá hlava obsahuje trojúhelník. Silná domněnka o dokonalých grafech byla prokázána pro grafy bez býčích hlav dávno před důkazem pro grafy obecného tvaru [2] a existuje známý algoritmus pro rozpoznání dokonalých grafů bez býčích hlav s polynomiální dobou běhu [3] .
Maria Chudnovskaya a Samuel Safra studovali bezhlavé grafy v obecnější podobě a ukázali, že každý takový graf musí mít buď velkou kliku , nebo velkou nezávislou množinu (to znamenápro grafy s býčí hlavou platí Erdős-Hajnalova domněnka ) [4 ] a vypracovali obecnou teorii struktury takových grafů [5] [6] [7] .
Chromatický polynom býčí hlavy je . Další dva grafy jsou chromaticky ekvivalentní býčí hlavě.
Charakteristickým polynomem grafu je .
Tattův polynom grafu je .