Graf utan trianglar

I grafteorin är en triangelfri graf en oriktad graf där inga tre hörn bildar en triangel av kanter. Triangelfria grafer kan också definieras som grafer med klicknummer ≤ 2, grafer med omkrets ≥ 4, grafer utan genererade 3-cykler , eller som lokalt oberoende grafer.

Enligt Turans teorem är en n -vertex triangelfri graf med maximalt antal kanter en komplett tvådelad graf där antalet hörn i varje del av grafen är så nära som möjligt.

En graf med 2n hörn och inga trianglar måste ha färre kanter.

Problemet med att hitta trianglar

Problemet med att hitta trianglar är problemet med att avgöra om en graf innehåller trianglar eller inte. Om grafen innehåller en triangel, uppmanas algoritmen ofta att mata ut tre hörn som bildar en triangel.

Det är möjligt att kontrollera om en graf med m kanter har trianglar i O( m 1,41 ) tid. [1] Ett annat tillvägagångssätt är att hitta spåret av matrisen A 3 , där A  är grafens närliggande matris . Spåret är noll om och endast om det inte finns några trianglar i grafen. För täta grafer är denna enkla matrismultiplikationsalgoritm mer effektiv eftersom den reducerar tidskomplexiteten till O( n 2,373 ), där n  är antalet hörn.

Som visas av Imrich, Klavžar och Mulder ( Imrich, Klavžar, Mulder 1999 ), är triangelfri grafigenkänning likvärdig i komplexitet med mediangrafigenkänning . Men för närvarande använder de bästa mediangrafalgoritmerna triangeligenkänning som en subrutin och inte vice versa.

Komplexiteten för beslutsträdet eller komplexiteten för frågan för problemet, där frågor till oraklet som kommer ihåg grafens närliggande matriser är lika med Θ( n 2 ). Men för kvantalgoritmer är den bästa nedre gränsen Ω( n ), men den mest kända algoritmen har en uppskattning av O( n 1,29 ) ( Belovs 2011 ).

Självständighetstalet och Ramsey-teorin

En oberoende uppsättning av hörn i en n - vertex triangelfri graf är lätt att hitta - antingen finns det en vertex med fler än grannar (i vilket fall grannarna bildar en oberoende mängd), eller så har alla hörn mindre än grannar (där fall varje största oberoende mängd måste ha åtminstone hörn) [2] . Denna gräns kan förbättras något - i alla grafer utan trianglar finns det en oberoende uppsättning med hörn, och i vissa grafer utan trianglar har alla oberoende uppsättningar hörn. [3] Ett sätt att skapa tegonfria grafer där alla oberoende uppsättningar är små är den triangelfria processen [ 4] , som skapar maximala triangelfria grafer genom att sekventiellt lägga till slumpmässigt valda kanter, vilket undviker skapandet av trianglar. Med en hög grad av sannolikhet bildar processen grafer med oberoende nummer . Man kan också hitta vanliga grafer med samma egenskaper. [5]

Dessa resultat kan också förstås som att man sätter de asymptotiska gränserna för Ramsey-talen R(3, t ) i formen  - om kanterna på en komplett graf med hörn är färgade röda och blå, så innehåller antingen den röda grafen en triangel, eller det finns inga trianglar i den, och då måste det finnas en oberoende uppsättning av storlek t som motsvarar en klick av denna storlek i den blå grafen.

Färglägga grafer utan trianglar

Mycket forskning om triangelfria grafer har fokuserat på graffärgning . Varje tvådelad graf (det vill säga vilken tvåfärgsbar graf som helst) har inte trianglar, och Grötzschs sats säger att vilken triangelfri plan graf som helst kan vara trefärgad. [6] Emellertid kan icke-plana grafer utan trianglar kräva mer än tre färger.

Mycielski ( 1955 ) definierade en konstruktion, nu kallad Mycielskian , som bildar en ny triangelfri graf från en annan triangelfri graf. Om en graf har kromatiskt nummer k har dess Mychelskian kromatiskt nummer k  + 1, så denna konstruktion kan användas för att visa att ett godtyckligt stort antal färger kan krävas för att färga en triangelfri icke-plan graf. I synnerhet är Grötzsch- grafen, en graf med 11 vertex bildad genom att upprepa Mycielskis konstruktion, en triangelfri graf som inte kan färgas med färre än fyra färger, och är den minsta grafen med dessa egenskaper. [7] Gimbel och Thomassen ( Gimbel, Thomassen & 2000 ) och ( Nilli 2000 ) visade att antalet färger som behövs för att färga en triangelfri m -linjegraf är

och det finns triangelfria grafer med kromatiska tal proportionella mot denna gräns.

Det finns också några resultat som rör sambandet mellan färgning och minimigraden av grafer utan trianglar. Andrásfai och Erdős ( Andrásfai, Erdős, Sós 1974 ) bevisade att varje n -vertex triangelfri graf där varje vertex har mer än en granne måste vara tvådelad. Detta är det bästa möjliga resultatet av denna typ, eftersom 5-cykeln kräver tre färger, men har exakt grannar för varje vertex. Uppmuntrade av detta resultat antog Erdős och Simonovits ( Erdős, Simonovits 1973 ) att varje triangelfri graf med n hörn, där varje vertex har åtminstone grannar, kan färgas med endast tre färger. Häggkvist ( 1981 ) motbevisade dock denna gissning genom att presentera ett motexempel där varje vertex i Grötsch-grafen ersätts av en oberoende uppsättning av speciellt vald storlek. Jin ( Jin 1995 ) visade att varje n -vertex triangelfri graf där varje vertex har mer än en granne kan vara 3-färgad. Detta är det bästa resultatet av denna typ, eftersom Haggquist-grafen kräver fyra färger och har exakta grannar för varje vertex. Slutligen bevisade Brandt och Thomassé ( Brandt, Thomassé 2006 ) att varje n -vertex triangelfri graf där vilken vertex som helst har fler än 4 grannar kan färgas med 4 färger. Ytterligare resultat av detta slag är omöjliga eftersom Hajnal [8] hittat exempel på triangelfria grafer med godtyckligt stort kromatiskt antal och minsta grad för någon .

Länkar

  1. ↑ Alon, Yuster, Zwick, 1994 .
  2. ↑ Boppana, Halldórsson, 1992 , som bygger på idén om Avi Wigdersons tidigare approximationsalgoritm ., sid. 184.
  3. ↑ Kim, 1995 .
  4. ↑ Erdős, Suen, Winkler, 1995 ; Bohman, 2008
  5. ↑ Alon, Ben-Shimon, Krivelevich, 2008 .
  6. ↑ Grötzsch, 1959 ; ( Thomassen 1994 )).
  7. ↑ Chvatal, 1974 .
  8. ↑ se Erdős, Simonovits, 1973 .
Källor