Föreskriven färg

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2022; kontroller kräver 5 redigeringar .

En föreskriven färgläggning  är en typ av graffärgning där varje vertex kan anta en begränsad uppsättning tillåtna färger. Weesing och Erdős var bland de första att studera denna färgning , liksom Rubin och Taylor [1] på 1970-talet.

Definition

Givet en graf G och en uppsättning L ( v ) av giltiga färger för varje vertex av V (kallad en lista ), är den föreskrivna färgningen  en urvalsfunktion som mappar varje vertex av V till en lista L(v) . Liksom med graffärgning antas den föreskrivna färgningen vara korrekt , vilket innebär att inga två närliggande hörn får samma färg. En graf sägs vara k -valbar (eller föreskriven - k -färgbar ) om den har rätt föreskriven färg, oavsett hur k- färgerna tilldelas varje vertex. Valnumret ( föreskriven färgbarhet , eller föreskrivet kromatiskt tal ) ch( G ) för en graf G  är det minsta talet k så att G är k -valbart.

Mer generellt, om den ges en funktion f som tilldelar ett positivt tal f ( v ) till varje vertex v , sägs en graf G vara f -valbar (eller föreskriven -f -färgbar ) om den har en föreskriven färgning oavsett hur listar f ( v ) färger för varje vertex v . I synnerhet, om för alla hörn v , motsvarar f -selektivitet k -selektivitet.

Exempel

Betrakta en komplett tvådelad graf med sex hörn A , B , W , X , Y , Z , så att A och B är anslutna till var och en av hörnen W , X , Y och Z och det finns inga andra kanter. Som för alla tvådelade grafer är det vanliga kromatiska antalet graf G 2 - du kan färga hörn A och B med en färg, och de återstående hörnen ( W , X , Y , Z ) med en annan färg, då kommer inga två närliggande hörn har samma färg. Å andra sidan har G ett föreskrivet kromatiskt tal större än 2, vilket visas av följande konstruktion: Tilldela hörn A och B listorna {röd, blå} och {grön, svart}. Tilldela listorna {röd, grön}, {röd, svart}, {blå, grön} och {blå, svart} till de andra fyra hörnen. Det spelar ingen roll vilket val som görs från listorna för hörn A och B , eftersom det finns några andra hörn för vilka båda färgerna i listan redan har använts. Grafen G är alltså inte 2-valbar.

Å andra sidan är det lätt att se att G är 3-valbart – att välja valfri färg för hörn A och B lämnar minst en giltig färg för varje återstående vertex.

Mer generellt, låt q vara ett positivt heltal och G vara en fullständig tvådelad graf . Låt de tillåtna färgerna representeras av olika tvåsiffriga tal i radix q -systemet (det vill säga i det q -ary-systemet). Låt en del, nämligen delen med q hörn, ges uppsättningar av färger s där de första tecknen är lika för varje val från q möjligheter att välja siffran i . Den andra delen av vertexgrafen ges färger , för vilka den första siffran är annorlunda för alla q - element. Illustrationen visar ett exempel på en sådan konstruktion med q  = 3.

Då har G ingen föreskriven färg för L  - oavsett vilken uppsättning färger som väljs för hörnen på den mindre sidan av den tvådelade grafen, kommer detta val att stå i konflikt med alla färger för en vertex på andra sidan av den tvådelade grafen. Till exempel, om en vertex med färguppsättningen {00,01} är färgad 01, och en vertex med färguppsättningen {10,11} är färgad 10, kan en vertex med färguppsättningen {01,10} inte färgas korrekt. Därför är det kromatiska talet för G minst [2] .

På liknande sätt, om , är den fullständiga tvådelade grafen inte k -valbar. För att visa detta, anta att det finns totalt tillgängliga färger, så att på ena sidan av den tvådelade grafen har varje vertex en annan uppsättning k färger för varje vertex. Sedan använder varje sida av den tvådelade grafen minst k färger för färgläggning. Annars måste det finnas en vertex där färguppsättningen skiljer sig från de som används. 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 det följer att två intilliggande hörn har samma färg. I synnerhet har den gemensamma grafen ett föreskrivet kromatiskt tal som inte är mindre än tre, och grafen har ett föreskrivet kromatiskt tal inte mindre än fyra [3] .

Egenskaper

För en graf G , låt beteckna det kromatiska numret och den maximala effekten av grafen G. Numret på den föreskrivna färgningen uppfyller följande egenskaper:

  1. . En graf som tillåter en föreskriven k -färgning måste i synnerhet ha en föreskriven färg om varje vertex tilldelas samma lista med k - färger, vilket motsvarar den vanliga k -färgningen;
  2. kan inte begränsas generellt i termer av det kromatiska numret, det vill säga det finns ingen funktion f så att den gäller för någon graf G . I synnerhet, som visas i exemplen på tvådelade grafer, finns det grafer med , för vilka godtyckligt stora [2] ;
  3. , där n är antalet hörn i grafen G [4] [4] ;
  4. [3] [5] ;
  5. , om G är en plan graf [6] ;
  6. , om G är en tvådelad plan graf [7] .

Beräkning av selektivitet och ( a , b )-selektivitet

Två algoritmiska problem tas upp i litteraturen:

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

Det är känt att problemet med k - selektivitet i tvådelade grafer är komplett för alla och detsamma gäller för 4-selektivitet i plana grafer, 3-selektivitet i plana grafer utan trianglar och (2, 3)-selektivitet i tvådelade plana grafer . grafer [8] [9] . För P5-fria grafer, det vill säga grafer utan 5 -vertex- vägar , är k -valbarhet ett -problem som kan lösas med fasta parametrar [10] .

Det är möjligt att kontrollera om en graf är 2-valbar i linjär tid genom att sekventiellt radera hörn med grad noll eller enhet tills vi får en 2-kärna av grafen, varefter sådana raderingar blir omöjliga. Den ursprungliga grafen är 2-vald om och endast om dess 2-kärna är antingen en jämn cykel eller en tetagraf som bildas av tre banor med gemensamma slutpunkter, två banor med längd två, och den tredje banan kan ha vilken jämn längd som helst [3] .

Applikationer

Den föreskrivna färgningen uppstår i praktiska problem rörande tilldelningen av frekvenskanaler [11] [12] .

Se även

Anteckningar

  1. ↑ Jensen, Toft, 1995 , sid. 18–21.
  2. ↑ 1 2 Gravier, 1996 , sid. 299–302.
  3. ↑ 1 2 3 Erdős, Rubin, Taylor, 1979 , sid. 125–157.
  4. ↑ 12 Eaton , 2003 .
  5. ↑ Vizing, 1976 , sid. 3–10.
  6. ↑ Thomassen, 1994 , sid. 180–181.
  7. ↑ Alon, Tarsi, 1992 , sid. 125–134.
  8. ↑ Gutner, 1996 , sid. 119–130.
  9. ↑ Gutner, Tarsi, 2009 , sid. 2260–2270.
  10. ↑ Heggernes och Golovach, 2009 , sid. 382–391.
  11. ↑ Wang, Liu, 2005 , sid. 690–694.
  12. ↑ Garg, Papatriantafilou och Tsigas, 1996 , sid. 18–25.

Litteratur

Läsning för vidare läsning