Cap de taur | |
---|---|
Vârfurile | 5 |
coaste | 5 |
Rază | 2 |
Diametru | 3 |
Circumferinţă | 3 |
Automorfisme | 2 ( Z /2 Z ) |
Număr cromatic | 3 |
Indicele cromatic | 3 |
Proprietăți |
Graficul planar Graficul distanței unității |
Capul de taur este un grafic plan nedirecționat cu 5 vârfuri și 5 muchii sub forma unui triunghi cu două muchii suspendate disjunse [1] .
Numărul cromatic al graficului este 3, indicele cromatic este 3, raza este 2, diametrul este 3 și circumferința este 3. Graficul este bloc , split , fără gheare , vârf -1 - conectat și 1- muchie -conectat .
Un grafic nu are capete de taur dacă capul nu este conținut ca subgraf generat de . Graficele fără triunghiuri sunt lipsite de capete de taur deoarece fiecare cap conține un triunghi. Conjectura puternică despre graficele perfecte a fost dovedită pentru graficele fără capete de taur cu mult înainte de demonstrarea pentru graficele de formă generală [2] , și există un algoritm binecunoscut pentru recunoașterea graficelor perfecte fără capete de taur cu timp de rulare polinomial [3] .
Maria Chudnovskaya și Samuel Safra au studiat graficele fără cap de taur într-o formă mai generală și au arătat că orice astfel de grafic trebuie să aibă fie o clică mare, fie o mulțime mare independentă (adică , conjectura Erdős-Hajnal este valabilă pentru graficele cu cap de taur). ) [4 ] și a dezvoltat o teorie generală a structurii unor astfel de grafice [5] [6] [7] .
Polinomul cromatic al capului de taur este . Celelalte două grafice sunt echivalente cromatic cu un cap de taur.
Polinomul caracteristic al graficului este .
Polinomul Tatta al graficului este .