Cap de taur (teoria graficelor)

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 .

Numărări libere din capete de taur

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] .

Polinoame cromatice și caracteristice

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 .

Note

  1. ^ Weisstein , Eric W. Bull Graph  pe site- ul Wolfram MathWorld .
  2. ↑ Chvatal, Sbihi, 1987 , p. 127–139.
  3. ↑ Reed, Sbihi, 1995 , p. 171–178.
  4. ↑ Chudnovsky, Safra, 2008 , p. 1301–1310.
  5. ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. I. Căi cu trei margini cu centre și anticentre , < http://www.columbia.edu/~mc2775/bulls1.pdf > Arhivat 3 martie 2016 la Wayback Machine . 
  6. ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. II. Elementary trigraphs , < http://www.columbia.edu/~mc2775/bulls2.pdf > Arhivat 4 martie 2016 la Wayback Machine . 
  7. ↑ Chudnovsky, M. (2008), The structure of bull-free graphs. III. Structura globală , < http://www.columbia.edu/~mc2775/bulls3.pdf > Arhivat la 3 martie 2016 la Wayback Machine . 

Literatură