Orienterad graffärgning

Riktad graffärgning är en speciell typ av graffärgning . Det är nämligen tilldelningen av färger till hörnen i en riktad graf [1] , som

En annan definition: En orienterad k -färgning av en digraf H är en orienterad homomorfism till en k -vertex-digraf H* [2] .

Orienterat kromatiskt tal

Det orienterade kromatiska talet för en digraf G är det minsta antalet färger som krävs i en orienterad färgning. Detta nummer betecknas vanligtvis som . Samma definition kan utökas till oriktade grafer genom att definiera det riktade kromatiska numret för en oriktat diagram som det maximala kromatiska antalet av alla dess orienteringar [3] [2] .

Exempel

Det orienterade kromatiska talet för en orienterad cykel med 5 hörn är fem. Om cykeln är färgad med fyra eller färre färger kommer antingen två angränsande hörn att färgas likadant, eller så kommer två hörn genom en att ha samma färg. I det senare fallet kommer kanterna som förbinder dessa två hörn med vertexen i mitten att vara felaktigt färgade (andra regeln) - båda bågarna har samma färgade ändar, men ansluter färgerna i motsatt riktning. Således är ingen färgläggning med fyra eller färre färger möjlig. Om vi ​​färgar alla hörn i olika färger får vi en tillåten orienterad färgning.

Egenskaper

En orienterad färgning kan endast existera för digrafer utan slingor och utan orienterade 2-cykler, eftersom en slinga ger en färg i båda ändarna av en båge, och en 2-cykel är inte tillåten enligt den andra regeln - två färger är sammankopplade i motsatta riktningar . Om dessa villkor är uppfyllda finns det alltid en orienterad färgning, till exempel om vi tilldelar olika färger till alla hörn.

Om en orienterad färgläggning är komplett , i den meningen att inga två färger kan slås samman till samma färg för att ge en korrekt färg, så motsvarar färgläggningen en enda turneringshomomorfism . Turneringen har ett hörn för varje färg i färgen. För varje färgpar finns det en båge i den färgade grafen med dessa två färger i ändarna, vilket motsvarar orienteringen av kanten i turneringen mellan hörnen på motsvarande färger. Ofullständiga färger kan också representeras av en turneringshomomorfism, men i detta fall är överensstämmelsen mellan färgningar och homomorfismer inte en-till-en.

Oriktade grafer med begränsat släkte , begränsat grad eller begränsat acykliskt kromatiskt nummer har också ett begränsat riktat kromatiskt nummer [3] .

Uppskattningar för det orienterade kromatiska talet

Det orienterade kromatiska numret för en graf kan skilja sig betydligt från dess (ordinarie) kromatiska tal. Till exempel finns det tvådelade grafer med ett godtyckligt stort orienterat kromatiskt tal, det räcker att ersätta varje kant av grafen med en bana med längden 2, och sedan måste ändarna av varje sådan bana i den resulterande grafen målas i olika färger [4] .

Courcelle [5] bevisade att för vilken plan graf som helst, och Raspud och Soupina [6] förbättrade resultatet till 80. Borodin et al publicerade följande teorem [7] :

Sats : Låt G vara en plan graf av g , sedan
(1) (2) (3) (4)


I en annan artikel av Borodin [8] mildrades begränsningen i (1) i satsen till 13.

Anteckningar

  1. ↑ I artikeln betyder en riktad graf en riktad graf. I den engelska versionen av Distels bok "Graph Theory" är orienterade grafer riktade grafer utan slingor eller flera kanter, det vill säga riktade grafer är riktade grafer utan slingor och multipla kanter, medan i den ryska översättningen av boken är riktade grafer riktade grafer utan slingor och flera kanter. Detta leder till frekvent förvirring
  2. ↑ 1 2 BORODIN, IVANOVA, 2005 , sid. 239.
  3. ↑ 1 2 Kostochka, Sopena, Zhu, 1997 , sid. 331–340.
  4. ↑ BORODIN, IVANOVA, 2005 , sid. 240.
  5. ↑ Courselle, 1994 .
  6. ↑ Raspaud, Sopena, 1994 , s. 171-174.
  7. ↑ Borodin, Kostochka, Nešetřil, Raspaud, Sopena, 1999 , s. 77-90.
  8. ↑ Borodin, Kim, Kostochka, West, 2004 , s. 147-159.

Litteratur