Listfärgning

I grafteori , en gren av matematik , är listfärgning en typ av graffärgning där varje hörn kan begränsas till en lista med tillåtna färger. Det studerades först på 1970-talet i oberoende tidningar av Vizing och av Erdős , Rubin och Taylor.

Definition

Givet en graf G och givet en uppsättning L ( v ) av färger för varje vertex v (kallad en lista ), är en listfärgning en valfunktion som mappar varje vertex v till en färg i listan L ( v ). Precis som med graffärgning antas en listfärgning i allmänhet vara korrekt , vilket betyder att inga två angränsande hörn får samma färg. En graf är k -valbar (eller k -list-colorable ) om den har en korrekt listfärgning oavsett hur man tilldelar en lista med k färger till varje vertex. Valbarheten (eller listfärgbarheten eller listkromatiskt tal ) ch( G ) för en graf G är det minsta talet k så att G är k -valbart.

Mer generellt, för en funktion f som tilldelar ett positivt heltal f ( v ) till varje vertex v , är en graf G f -valbar (eller f -list-färgbar ) om den har en listfärgning oavsett hur man tilldelar en lista med f ( v ) färger till varje vertex v . Speciellt om för alla hörn v , motsvarar f -valbarhet k -valbarhet.

Exempel

Betrakta den fullständiga tvådelade grafen G = K 2,4 , med sex hörn A , B , W , X , Y , Z så att A och B var och en är kopplade till alla W , X , Y och Z , och inga andra hörn är anslutna. Som en tvådelad graf G det vanliga kromatiska nummer 2: man kan färga A och B i en färg och W , X , Y , Z i en annan och inga två närliggande hörn kommer att ha samma färg. Å andra sidan G ett listkromatiskt tal större än 2, vilket följande konstruktion visar: tilldela A och B listorna {röd, blå} och {grön, svart}. Tilldela de andra fyra hörnen listorna {röd, grön}, {röd, svart}, {blå, grön} och {blå, svart}. Oavsett vilket val man gör av en färg från listan över A och en färg från listan över B , kommer det att finnas någon annan vertex så att båda dess val redan används för att färga sina grannar. G är alltså inte 2-valbar.

Å andra sidan är det lätt att se att G är 3-valbart: att välja godtyckliga färger för hörnen A och B lämnar minst en tillgänglig färg för var och en av de återstående hörnen, och dessa färger kan väljas godtyckligt.

En listfärgningsinstans på den kompletta tvådelade grafen K 3,27 med tre färger per vertex. Oavsett vilka färger som väljs för de tre centrala hörnen, kommer en av de yttre 27 hörnen att vara ofärgbar, vilket visar att det kromatiska numret på K 3,27 är minst fyra.

Mer generellt, låt q vara ett positivt heltal och låt G vara den fullständiga tvådelade grafen K q , q q . Låt de tillgängliga färgerna representeras av de q 2 olika tvåsiffriga talen i radix q . På ena sidan av bipartitionen, låt q -hörnen ges uppsättningar av färger { i 0, i 1, i 2, ... } där de första siffrorna är lika med varandra, för vart och ett av de q möjliga valen av första siffran i . På andra sidan av bipartitionen, låt q q hörn ges uppsättningar av färger {0 a , 1 b , 2 c , ... } där de första siffrorna alla är distinkta, för vart och ett av de q q möjliga valen av q - tupeln ( a , b , c , ...). Illustrationen visar ett större exempel på samma konstruktion, med q = 3.

Då har G ingen listfärgning för L : oavsett vilken uppsättning färger som väljs för hörnen på den lilla sidan av bipartitionen, kommer detta val att stå i konflikt med alla färgerna för en av hörnen på andra sidan av bipartitionen. Till exempel om vertex med färguppsättning {00,01} är färgad 01, och vertex med färguppsättning {10,11} är färgad 10, då kan vertex med färguppsättning {01,10} inte färgas. Därför är listans kromatiska nummer för G minst q + 1.

På liknande sätt, om så är den fullständiga tvådelade grafen K n , n inte k -valbar. För, anta att 2 k − 1 färger är tillgängliga totalt, och att, på en enda sida av bipartitionen, varje vertex har en annan k -tuppel av dessa färger tillgängligt än varje annan vertex. Sedan måste varje sida av bipartitionen använda minst k färger, eftersom varje uppsättning av k − 1 färger kommer att vara osammanhängande från listan med en vertex. Eftersom minst k färger används på ena sidan och minst k används på den andra, måste det finnas en färg som används på båda sidor, men detta innebär att två intilliggande hörn har samma färg. I synnerhet verktygsgrafen K 3,3 listkromatiskt nummer minst tre och grafen K 10,10 har listkromatiskt nummer minst fyra.

Egenskaper

För en graf G , låt χ( G ) beteckna det kromatiska talet och Δ( G ) den maximala graden av G . Listfärgsnumret ch( G ) uppfyller följande egenskaper.

  1. ch( G ) ≥ χ( G ). En k -list-färgbar graf måste i synnerhet ha en listfärgning när varje vertex tilldelas samma lista med k- färger, vilket motsvarar en vanlig k -färgning.
  2. ch( G ) kan inte begränsas i termer av kromatiskt tal i allmänhet, det vill säga det finns ingen funktion f så att ch( G ) ≤ f (χ( G )) gäller för varje graf G . I synnerhet, som exemplen på kompletta tvådelade grafer visar, finns det grafer med χ( G ) = 2 men med ch( G ) godtyckligt stor.
  3. ch( G ) ≤ χ( G ) ln( n ) där n är antalet hörn av G .
  4. ch( G ) ≤ Δ( G ) + 1.
  5. ch( G ) ≤ 5 om G är en plan graf .
  6. ch( G ) ≤ 3 om G är en tvådelad plan graf.

Beräkningsvalbarhet och ( a , b )-valbarhet

Två algoritmiska problem har övervägts i litteraturen:

  1. k - valbarhet : bestäm om en given graf är k -valbar för en given k , och
  2. ( a , b )- valbarhet : avgör om en given graf är f -valbar för en given funktion .

Det är känt att k -valbarhet i tvådelade grafer är -komplett för alla k ≥ 3, och detsamma gäller för 4-valbarhet i plana grafer, 3- valbarhet i plana triangelfria grafer och (2, 3)-valbarhet i tvådelade plana grafer. För P 5 -fria grafer, det vill säga grafer exklusive en 5-vertex- banagraf , är k - valbarheten trakterbar med fasta parametrar .

Det är möjligt att testa om en graf är 2-valbar i linjär tid genom att upprepade gånger ta bort hörn av grad noll eller ett tills man når grafens 2-kärna , varefter inga fler sådana raderingar är möjliga. Den initiala grafen är 2-valbar om och endast om dess 2-kärna antingen är en jämn cykel eller en tetagraf som bildas av tre banor med delade slutpunkter, med två banor med längd två och den tredje banan har någon jämn längd.

Ansökningar

Listfärgning uppstår i praktiska problem kring kanal-/frekvenstilldelning.

Se även

  1. ^   Jensen, Tommy R.; Toft, Bjarne (1995), "1.9 List coloring", Graph coloring problems , New York: Wiley-Interscience, s. 18–21, ISBN 0-471-02865-7
  2. ^ a b   Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics , 152 (1–3): 299–302, doi : 10.1016/0012-365X(95)00350-6 , MR 1388650 .
  3. ^ a b c Erdős, P. ; Rubin, AL ; Taylor, H. (1979), "Choosability in graphs", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata (PDF) , Congressus Numerantium, vol. 26, s. 125–157, arkiverad från originalet (PDF) 2016-03-09 , hämtad 2008-11-10
  4. ^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1" (PDF) , Talk , arkiverad från originalet (PDF) den 29 augusti 2017 , hämtad 29 maj 2010
  5. ^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2" (PDF) , Talk , arkiverad från originalet (PDF) den 30 augusti 2017 , hämtad 29 maj 2010
  6. ^ Vizing, VG (1976), "Vertexfärgningar med givna färger", Metody Diskret. Analiz. (på ryska), 29 : 3–10
  7. ^ Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B , 62 : 180–181, doi : 10.1006/jctb.1994.1062
  8. ^ Alon, Noga ; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica , 12 (2): 125–134, doi : 10.1007/BF01204715
  9. ^ Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics , 159 (1): 119–130, arXiv : 0802.2668 , doi : 10.1016/0012-365X(95) 5 .
  10. ^ Gutner, Shai; Tarsi, Michael (2009), "Some results on ( a : b )-choosability", Discrete Mathematics , 309 (8): 2260–2270, doi : 10.1016/j.disc.2008.04.061
  11. ^ Heggernes, Pinar ; Golovach, Petr (2009), "Choosability of P 5 -free graphs" (PDF) , Mathematical Foundations of Computer Science , Lecture Notes on Computer Science, vol. 5734, Springer-Verlag, s. 382–391
  12. ^ Wang, Wei; Liu, Xin (2005), "List-coloring based channel allocation for open-spectrum wireless networks", 2005 IEEE 62nd Vehicular Technology Conference (VTC 2005-Fall), vol. 1, s. 690–694, doi : 10.1109/VETECF.2005.1558001 .
  13. ^ Garg, N.; Papatriantafilou, M.; man dynamiskt allokerar frekvenser till mobila basstationer", Åttonde IEEE Symposium on Parallel and Distributed Processing , s. 18–25, doi : 10.1109/SPDP.1996.570l.1: 21112 : 11312 : 1996.570l . /0000-0001-1AE6-F .

Vidare läsning