Tyrehoved (grafteori)

Tyrehoved
Toppe 5
ribben 5
Radius 2
Diameter 3
Omkreds 3
Automorfismer 2 ( Z /2 Z )
Kromatisk tal 3
Kromatisk indeks 3
Ejendomme Planar
graf enhed
afstand graf

Tyrens hoved er en plan urettet graf med 5 hjørner og 5 kanter i form af en trekant med to usammenhængende kanter [1] .

Grafens kromatiske tal er 3, det kromatiske indeks er 3, radius er 2, diameteren er 3, og omkredsen er 3. Grafen er blok , split , kloløs , toppunkt -1-forbundet og 1 - kant -forbundet .

Tæller fri for tyrehoveder

En graf er fri for tyrehoveder, hvis hovedet ikke er indeholdt som en genereret undergraf af . Grafer uden trekanter er fri for tyrehoveder, fordi hvert hoved indeholder en trekant. Den stærke formodning om perfekte grafer blev bevist for grafer uden tyrehoveder længe før beviset for grafer af generel form [2] , og der er en velkendt algoritme til at genkende perfekte grafer uden tyrehoveder med polynomisk køretid [3] .

Maria Chudnovskaya og Samuel Safra studerede grafer uden tyrehoved i en mere generel form og viste, at enhver sådan graf skal have enten en stor klike eller et stort uafhængigt sæt (det vil sige , Erdős-Hajnal-formodningen gælder for tyrehovedgrafer ) [4 ] og udviklede en generel teori om strukturen af ​​sådanne grafer [5] [6] [7] .

Kromatiske og karakteristiske polynomier

Det kromatiske polynomium af tyrens hoved er . De to andre grafer svarer kromatisk til et tyrehoved.

Grafens karakteristiske polynomium er .

Grafens Tatta-polynomium er .

Noter

  1. ↑ Weisstein, Eric W. Bull Graph  på Wolfram MathWorld- webstedet .
  2. ↑ Chvatal, Sbihi, 1987 , s. 127-139.
  3. ↑ Reed, Sbihi, 1995 , s. 171-178.
  4. ↑ Chudnovsky, Safra, 2008 , s. 1301-1310.
  5. ↑ Chudnovsky, M. (2008), Strukturen af ​​tyrefrie grafer. I. Trekantede stier med centre og anticentre , < http://www.columbia.edu/~mc2775/bulls1.pdf > Arkiveret 3. marts 2016 på Wayback Machine . 
  6. ↑ Chudnovsky, M. (2008), Strukturen af ​​tyrefrie grafer. II. Elementære trigrafer , < http://www.columbia.edu/~mc2775/bulls2.pdf > Arkiveret 4. marts 2016 på Wayback Machine . 
  7. ↑ Chudnovsky, M. (2008), Strukturen af ​​tyrefrie grafer. III. Global struktur , < http://www.columbia.edu/~mc2775/bulls3.pdf > Arkiveret 3. marts 2016 på Wayback Machine . 

Litteratur