Enhetlig färgning

Enhetlig färgning  är tilldelningen av färger till hörnen på en oriktad graf på ett sådant sätt att:

Det vill säga att dela upp hörnen i olika färger är så enhetligt som möjligt. Till exempel att ge varje vertex en annan färg skulle vara en enhetlig färg, men skulle vanligtvis använda många fler färger än vad som behövs för en optimal enhetlig färgning. Ett likvärdigt sätt att definiera en enhetlig färg är att bädda in en given graf som en subgraf i en Turan-graf med samma uppsättning hörn. Det finns två sorters kromatiska tal förknippade med enhetlig färgning [1] . Det enhetliga kromatiska talet för en graf G  är det minsta antalet k så att grafen G har en enhetlig färg med k färger. Emellertid kanske grafen G inte har enhetliga färger för vissa större uppsättningar färger. Den enhetliga kromatiska tröskeln för en graf G  är det minsta antalet k så att graf G har enhetliga färger för vilket antal färger som helst som är större än eller lika med k [2] .

Hajnal-Szemeredy-satsen , som formulerades som en gissning av Pal Erdős [3] och bevisad av András Hajnal och Endre Szemeredy [4] , säger att varje graf med en maximal grad har en enhetlig färgning med färger. Flera relaterade hypoteser förblir öppna. Det finns även polynomiska tidsalgoritmer för att hitta en färgning som motsvarar denna gräns [5] , samt algoritmer för att hitta optimala färger för speciella klasser av grafer, men ett mer generellt problem med att avgöra om en godtycklig graf har en enhetlig färgning med en given antal färger är NP-komplett .

Exempel

Stjärnan K 1.5 som visas i figuren är en komplett tvådelad graf , och kan därför färgas med två färger. Den resulterande färgningen har emellertid en spets av en färg och fem spetsar av en annan färg, och därför är färgningen inte enhetlig. Det minsta antalet färger i en enhetlig färgning av denna graf är fyra, som visas i figuren - det centrala hörnet måste tillhöra en klass med en enda vertex, så de andra fem hörnen måste delas upp i minst tre färger så att varje klass innehåller högst två hörn. Mer allmänt noterade Meyer [6] att varje stjärna K 1, n kräver färger för enhetlig färgning, och därför kan det kromatiska numret på en graf inte skilja sig från dess kromatiska enhetliga nummer med högst n /4 gånger. Eftersom K 1,5 har en maximal grad av fem, är antalet färger som garanteras av Hajnal-Szemeredis sats sex, vilket erhålls genom att tilldela en annan färg till varje vertex.

Ett annat intressant fenomen visar en annan komplett tvådelad graf, . Denna graf har en enhetlig 2-färgning som definieras av dess bipartite. Den har dock inte en enhetlig (2 n  + 1)-färgning - varje enhetlig uppdelning av hörn i detta antal färger skulle behöva ha exakt två hörn per färg, men de två delarna av en tvådelad graf kan inte paras ihop eftersom de innehåller ett udda antal hörn. Därför är den enhetliga kromatiska tröskeln för denna graf , vilket är mycket större än dess enhetliga kromatiska tal, som är två.

Hainal-Semeredis sats

Brooks teorem säger att varje sammankopplad graf med maximal grad är -färgbar, med två undantag ( kompletta grafer och udda cykler). Men denna färgning kan i allmänhet vara långt ifrån enhetlig. Pal Erdős [3] förmodade att en enhetlig färgning är möjlig med bara en komplementär färg – vilken graf som helst med maximal grad har en enhetlig färgning med färger. Fodralet är enkelt (vilken kombination av banor och slingor som helst kan färgas enhetligt med trefärgade repeterande mönster, med små justeringar för slutna slingor). Fallet avgjordes av Corradi och Hainal [7] . Den fullständiga gissningen bevisades av Hajnal och Semeredi [4] och är nu känd som Hajnal-Szemeredis teorem. Deras ursprungliga bevis var långa och komplicerade. Ett enklare bevis gavs av Kirsted och Kostochka [8] . En polynomisk tidsalgoritm för att hitta enhetliga färger med detta antal färger beskrevs av Kiersted och Kostochka. De tillskriver Marcelo Midlarz och Endre Szemeredi en annan, tidigare utvecklad, opublicerad polynomtidsalgoritm. Kiersted och Kostochka tillkännagav också en starkare version av satsen att en enhetlig k -färgning existerar om graderna av två angränsande hörn som mest summerar till , men beviset publicerades aldrig.

Meyer [6] gissade i form av Brooks enhetliga färgsats att varje sammankopplad graf med maximal grad har en enhetlig färgning med eller färre färger, förutom kompletta grafer och udda cykler. En starkare version av gissningarna säger att varje sådan graf har en enhetlig färg med exakta färger, med undantag för en komplett tvådelad graf där båda delarna har samma udda antal hörn [1] .

Seymour [9] föreslog en förstärkning av Hajnal-Szemeredis sats, som också inkluderar Diracs sats att täta grafer är Hamiltonska  - han antog att om någon vertex i en graf med n hörn har åtminstone grannar, så innehåller grafen som en subgraf graf som bildas genom att koppla samman hörn som är högst k steg bort i en n -cykel. Fallet k  = 1 är Diracs eget teorem. Hajnal-Szemeredis sats kan åsidosättas av denna hypotes genom att tillämpa hypotesen för stora värden på k på komplementet till grafen och använda kontinuerliga sekvenser av hörn från n -cykeln som färgklasser . Seymours gissning har bevisats för grafer där n är tillräckligt stort jämfört med k [10] . Beviset använder några djupa medel, inklusive Hajnal-Szemeredis sats själv.

En annan generalisering av Haynal-Szemeredis sats är Bollobash-Eldridge-Katlin-hypotesen (eller, för kort, BEC-hypotesen) [11] . Den anger att om G 1 och G 2 är n -vertexgrafer med maximal grad respektive , och om , så kan G 1 och G 2 packas. Det vill säga, G 1 och G 2 kan representeras på samma uppsättning av n hörn utan gemensamma kanter. Hajnal-Szemeredi-satsen är ett specialfall av gissningarna där G 2 är föreningen av osammanhängande klickar . Catlin [12] ger ett liknande men starkare villkor på och under vilket en sådan packning garanterat existerar.

Särskilda fall av grafer

För något träd med maximal grad överstiger inte det enhetliga kromatiska talet

[6]

med värsta fall på en stjärna. De flesta träd har dock ett mycket mindre enhetligt kromatiskt nummer - om ett träd med n hörn har , då har det en enhetlig färg med bara tre färger [13] . Furmanchik [1] studerade det enhetliga kromatiska antalet produkter av grafer .

Beräkningskomplexitet

Problemet med att hitta enhetliga färger med så få färger som möjligt (under Hainal-Semeredi-gränsen) studerades också. En direkt reduktion från en graffärgning till en enhetlig färgning kan bevisas genom att lägga till tillräckligt många isolerade hörn till grafen, vilket visar att testet om en graf har en enhetlig färgning med ett givet antal färger (större än två) är NP-komplett . Problemet blir dock mer intressant när det begränsas till en speciell klass av grafer eller i termer av parameteriserad komplexitet . Bodlander och Fomin [14] visade att givet en graf G och ett antal färger c , kan man kontrollera om G kan vara enhetligt c -färgad i O( n O( t ) ) tid, där t  är trädets bredd på G . I synnerhet kan enhetlig färgning lösas optimalt i polynomtid för träd (som är känt tack vare Chen och Lee [15] ) och ytterplanära grafer . Det finns också en polynomisk tidsalgoritm för enhetlig färgning av delade grafer [16] . Fellowes, Fomin, Lokshtanov et al [17] visade dock att när trädbredden är en algoritmparameter är problemet W[1]-hårt. Det är således osannolikt att det finns en polynomtidsalgoritm som är oberoende av denna parameter, eller ens att beroendet av parametern kan placeras inom parentes av exponenten i löptidsformeln.

Applikationer

En av anledningarna till att överväga enhetlig färgning föreslogs av Meyer [6] i samband med schemaläggningsproblem . I den här applikationen representerar grafens hörn en uppsättning uppgifter som ska utföras, och kanterna förbinder två uppgifter som inte kan utföras samtidigt. Färgen på denna graf representerar uppdelningen av uppgifter i delmängder som kan utföras samtidigt. Då motsvarar antalet färger i färgläggningen antalet steg som krävs för att slutföra uppgiften helt. Enligt lastbalanseringskonventioner är det önskvärt att utföra samma eller nästan samma antal uppgifter i varje steg, och denna balansering är precis vad enhetlig färgning ger. Furmanchik [1] nämnde en specifik tillämpning av denna typ av schemaläggningsproblem, nämligen fördelningen av universitetskurser efter akademiska timmar så att kurserna fördelas lika över de tillgängliga tidsluckor, för att undvika att tilldela inkompatibla kurspar till samma tid.

Hajnal-Szemeredis sats har också använts för att begränsa variansen av summor av slumpvariabler med begränsat beroende [18] [19] . Om (som i tillståndet för det lokala Lovas-lemmat ) varje variabel är beroende av högst andra, kan enhetlig färgning av beroendegrafen användas för att dela upp variablerna i oberoende delmängder inom vilka Chernoff-gränser kan beräknas , vilket ger bättre gränser för variansen än om den är uppdelad på ett olikformigt sätt.

Anteckningar

  1. ↑ 1 2 3 4 Furmańczyk, 2006 .
  2. ↑ Observera att när k är större än antalet hörn i grafen, finns det alltid en enhetlig färgning med k färger där alla färgklasser har noll eller en vertex per klass, så att varje graf har en enhetlig kromatisk tröskel.
  3. ↑ 12 Erdős , 1964 .
  4. ↑ 1 2 Hajnal, Szemerédi, 1970 .
  5. ↑ Kierstead, Kostochka, Mydlarz, Szemerédi, 2010 , sid. 217–224.
  6. ↑ 1 2 3 4 Meyer, 1973 .
  7. ↑ Corrádi, Hajnal, 1963 .
  8. ↑ Kierstead, Kostochka, 2008 .
  9. ↑ Seymour, 1974 .
  10. ↑ Komlós, Sárközy, Szemerédi, 1998 .
  11. ↑ Bollobás, Eldridge, 1978 .
  12. ↑ Catlin, 1974 .
  13. ↑ Bollobás, Guy, 1983 .
  14. ↑ Bodlaender, Fomin, 2005 .
  15. ↑ Chen, Lih, 1994 .
  16. ↑ Chen, Ko, Lih, 1996 .
  17. ↑ Fellows, Fomin, Lokshtanov, 2007 .
  18. ↑ Pemmaraju, 2001 .
  19. ↑ Janson, Ruciński, 2002 .

Litteratur

Länkar