Hadwiger-antagande (grafteori) - Hadwiger conjecture (graph theory)

Se även: Hadwiger-gissningar (kombinatorisk geometri)
Olöst problem i matematik :

Har varje graf med kromatiskt tal en -vertex komplett graf som mindre ?

(mer olösta problem i matematik)
En graf som kräver fyra färger i vilken färg som helst, och fyra anslutna underbilder som, när de är sammandragna, bildar en komplett graf, som illustrerar fallet k  = 4 av Hadwigers förmodning

I grafteori , den Hadwiger förmodar stater att om G är loopless och har ingen mindre sedan dess kromatiska antal uppfyller . Det är känt att det är sant för . Antagandet är en generalisering av fyrfärgssatsen och anses vara ett av de viktigaste och mest utmanande öppna problemen inom området.

Mer detaljerat, om alla korrekta färgningar av en oriktad graf G använder k eller fler färger, kan man hitta k oskilda anslutna underbilder av G så att varje underbild är ansluten med en kant till varandra underbild. Contracting kanterna inom varje av dessa subgrafer så att varje subgraf kollapsar till en enda vertex producerar en komplett graf K k på k vertex som en mindre av G .

Denna antagande, en långtgående generalisering av fyrfärgsproblemet , gjordes av Hugo Hadwiger 1943 och är fortfarande olöst. Bollobás, Catlin & Erdős (1980) kallar det ”ett av de djupaste olösta problemen i grafteorin.”

Motsvarande former

En ekvivalent form av Hadwiger-antagandet ( kontrapositivet för den ovan angivna formen) är att om det inte finns någon sekvens av kantkontraktioner (var och en slår samman de två ändpunkterna för någon kant till en enda supervertex) som tar en graf G till hela grafen K k , då måste G ha en toppfärgning med k  - 1 färger.

Observera att, i en minimal k -coloring av någon graf G , contracting varje färgklass av färgnings till en enda vertex kommer att producera en komplett graf K k . Denna sammandragningsprocess producerar emellertid inte en mindre av G eftersom det (per definition) inte finns någon kant mellan några två hörn i samma färgklass, varför sammandragningen inte är en kantkontraktion (vilket krävs för minderåriga). Hadwigers antagande säger att det finns ett annat sätt att ordentligt kanta sammandragande uppsättningar av hörn till enstaka hörn, vilket ger ett komplett diagram K k , på ett sådant sätt att alla kontraherade uppsättningar är anslutna.

Om F k betecknar familjen av grafer som har den egenskapen att alla minderåriga diagram i F k kan vara ( k  - 1) -färgade, så följer det av Robertson – Seymour-satsen att F k kan karakteriseras av en begränsad uppsättning förbjuden minderåriga . Hadwigers antagande är att denna uppsättning består av en enda förbjuden mindreårig, K k .

Den Hadwiger Nummer h ( G ) hos en graf G är storleken k av den största komplett graf K k som är en mindre av G (eller ekvivalent kan erhållas genom avtals kanter G ). Det är också känt som den kontraktion klick antal av G . Den Hadwiger gissningar kan anges i den enkla algebraiska formen χ ( G ) ≤  h ( G ), där χ ( G ) betecknar den kromatiska antal av G .

Särskilda fall och partiella resultat

Fallet k  = 2 är trivialt: en graf kräver mer än en färg om och endast om den har en kant, och att kanten är i sig ett K 2 mindre. Fallet k  = 3 är också enkelt: graferna som kräver tre färger är icke- bipartitgraferna , och varje icke-bipartitgraf har en udda cykel , som kan kontraktas till en 3-cykel, det vill säga en K 3- minor.

I samma papper där han introducerade antagandet bevisade Hadwiger sin sanning för k  ≤ 4. Graferna utan K 4- moll är serie-parallella grafer och deras underbilder. Varje graf av denna typ har ett toppunkt med högst två infallande kanter; man kan trefärga vilken graf som helst genom att ta bort ett sådant toppunkt, färga kvarvarande graf rekursivt och sedan lägga till tillbaka och färglägga det borttagna toppunktet. Eftersom det borttagna toppunktet har högst två kanter, kommer en av de tre färgerna alltid att vara tillgängliga för att färga det när toppunkten läggs tillbaka.

Sanningen av gissningar för k  = 5 innebär fyrfärgssatsen : för om gissningar är sant, skulle varje kurva kräver fem eller flera färger har en K 5 mindre och skulle (av Wagners sats ) vara icke plan. Klaus Wagner bevisade 1937 att fallet k  = 5 egentligen motsvarar fyrfärgssatsen och därför vet vi nu att det är sant. Som Wagner visade kan varje graf som inte har K 5- moll sönderdelas via klicksummor i bitar som antingen är plana eller en 8-vertex Möbius-stege , och var och en av dessa bitar kan vara fyrfärgade oberoende av varandra, så 4-colorability av en K 5 -minor fritt graf följer av 4-colorability av var och en av de plana bitar.

Robertson, Seymour & Thomas (1993) bevisade antagandet för k  = 6, även med fyrfärgssatsen; deras papper med detta bevis vann Fulkersonpriset 1994 . Det följer av deras bevis att länklöst inbäddade grafer , en tredimensionell analog av plana grafer, har högst fem kromatiska tal. På grund av detta resultat är antagandet känt för att vara sant för k  ≤ 6, men det förblir olöst för alla k  > 6.

För k  = 7 är några partiella resultat kända: varje 7-kromatisk graf måste innehålla antingen en K 7- minor eller båda en K 4,4- minor och en K 3,5- minor.

Varje graf G har ett toppunkt med högst O ( h ( G )  √ log h ( G ) ) infallande kanter, varifrån det följer att en girig färgningsalgoritm som tar bort detta låggradiga toppunkt, färger kvarvarande graf och sedan lägger till tillbaka det borttagna toppunktet och färgar det, färgar den givna grafen med O ( h ( G )  √ log h ( G ) ) färger.

På 1980-talet bevisade båda Alexander V. Kostochka och Andrew Thomason självständigt att varje graf utan mindreåriga har en genomsnittlig grad och därmed kan färgas med färger. Detta resultat har senare förbättrats av Sergey Norin, Zi-Xia Song och Luke Postle till färger för alla . 2020 tillkännagav Postle ytterligare en förbättring av -färgbarhet för grafer utan -minor.

Van der Zypen (2012) har konstruerat en graf H med χ (H) =  ω men ingen K ω mindre, vilket visar att antagandet inte håller för grafer med oändligt oändligt färgnummer.

Generaliseringar

György Hajós antog att Hadwigers antagande kunde stärkas till underindelningar snarare än minderåriga: det vill säga att varje graf med kromatiskt tal k innehåller en indelning av en komplett graf K k . Hajós 'gissning är sant för k ≤ 4, men Catlin (1979) fann motexempel till denna förstärkta gissning för k  ≥ 7; fallen k  = 5 och k  = 6 förblir öppna. Erdős & Fajtlowicz (1981) observerade att Hajoss gissning misslyckas dåligt för slumpmässiga grafer : för alla ε> 0, i gränsen när antalet hörn, n , går till oändlighet, närmar sig sannolikheten en som en slumpmässig n- vertikalgraf har kromatiskt tal ≥ (1/2 - ε) n  / log 2  n , och att dess största klickindelning har högst cn 1/2 hörn för någon konstant c . I detta sammanhang är det värt att notera att sannolikheten också närmar sig en att ett slumpmässigt n- vertikalt diagram har Hadwiger-tal större än eller lika med sitt kromatiska tal, så Hadwiger-antagandet gäller för slumpmässiga grafer med hög sannolikhet; närmare bestämt är Hadwiger-talet med stor sannolikhet konstanta gånger n / √ log  n .

Borowiecki (1993) frågade om Hadwigers antaganden kunde utvidgas till att omfatta färgläggning . För k  ≤ 4 har varje graf med listkromatiskt nummer k en k- vertikal klickmoll. Dock är det maximala listan kromatiska antal plana grafer 5, inte fyra, så förlängningen misslyckas redan för K 5 -minor fria grafer. Mer allmänt finns det för varje t  ≥ 1 grafer vars Hadwiger-tal är 3 t  + 1 och vars lista kromatiska tal är 4 t  + 1.

Gerards och Seymour antog att varje graf G med kromatiskt tal k har en komplett graf K k som en udda minor . En sådan struktur kan representeras som en familj av k -ryggradssammanhängande underträd av G , som var och en är tvåfärgad, så att varje par av underträd är förbundna med en monokromatisk kant. Även om grafer utan udda K k- moll inte nödvändigtvis är glesa , gäller en liknande övre gräns för dem som den gör för den vanliga Hadwiger-gissningen: en graf utan udda K k- moll har kromatiskt tal χ ( G ) = O (k  √ log  k ).

Genom att införa extra villkor för G kan det vara möjligt att bevisa förekomsten av större minderåriga än K k . Ett exempel är snark sats , att varje kubik graf som kräver fyra färger i alla kant färg har Petersen grafen som en mindre, gissade av WT tutte och meddelade att bevisas i 2001 av Robertson, Sanders, Seymour och Thomas.

Anteckningar

Referenser