Orienteret graffarvning

Målrettet graffarvning er en speciel form for graffarvning . Det er nemlig tildelingen af ​​farver til hjørnerne af en rettet graf [1] , som

En anden definition: En orienteret k -farvning af en digraf H er en orienteret homomorfi til en k -vertex- digraf H* [2] .

Orienteret kromatisk tal

Det orienterede kromatiske tal for en digraf G er det mindste antal farver, der kræves i en orienteret farvning. Dette tal betegnes normalt som . Den samme definition kan udvides til urettede grafer ved at definere det rettede kromatiske tal for en urettet graf som det maksimale kromatiske antal af alle dens orienteringer [3] [2] .

Eksempler

Det orienterede kromatiske tal for en orienteret cyklus med 5 hjørner er fem. Hvis cyklussen er farvet med fire eller færre farver, vil enten to tilstødende hjørner være farvet ens, eller to spidser gennem en vil have samme farve. I sidstnævnte tilfælde vil kanterne, der forbinder disse to toppunkter med toppunktet i midten, være forkert farvet (anden regel) - begge buer har samme farvede ender, men forbinder farverne i den modsatte retning. Det er således ikke muligt at farvelægge med fire eller færre farver. Hvis vi farver alle hjørnerne i forskellige farver, får vi en tilladt orienteret farvning.

Egenskaber

En orienteret farvning kan kun eksistere for digrafer uden løkker og uden orienterede 2-cyklusser, da en løkke giver én farve i begge ender af en bue, og en 2-cyklus er ikke tilladt ifølge den anden regel - to farver er forbundet i modsatte retninger . Hvis disse betingelser er opfyldt, er der altid en orienteret farvning, for eksempel hvis vi tildeler forskellige farver til alle hjørner.

Hvis en orienteret farvning er komplet , i den forstand, at ingen to farver kan smeltes sammen til den samme farve for at give en ordentlig farve, så svarer farvningen til en enkelt turneringshomomorfi . Turneringen har et toppunkt for hver farve i farvelægningen. For hvert farvepar er der en bue i den farvede graf med disse to farver i enderne, som svarer til orienteringen af ​​kanten i turneringen mellem hjørnerne af de tilsvarende farver. Ufuldstændige farvninger kan også repræsenteres af en turneringshomomorfi, men i dette tilfælde er overensstemmelsen mellem farvninger og homomorfismer ikke en-til-en.

Urettede grafer med afgrænset slægt , afgrænset grad eller afgrænset acyklisk kromatisk tal har også afgrænset rettet kromatisk tal [3] .

Estimater for det orienterede kromatiske tal

Det orienterede kromatiske tal på en graf kan afvige væsentligt fra dets (almindelige) kromatiske tal. For eksempel er der todelte grafer med et vilkårligt stort orienteret kromatisk tal, det er nok at erstatte hver kant af grafen med en sti med længde 2, og så skal enderne af hver sådan sti i den resulterende graf males i forskellige farver [4] .

Courcelle [5] beviste, at for enhver plan graf, og Raspud og Soupina [6] forbedrede resultatet til 80. Borodin et al. offentliggjorde følgende teorem [7] :

Sætning : Lad G være en plan graf af g , så
(1) (2) (3) (4)


I en anden artikel af Borodin [8] blev begrænsningen i (1) af teoremet lempet til 13.

Noter

  1. ↑ I artiklen betyder en rettet graf en rettet graf. I den engelske version af Distels bog "Graph Theory" er orienterede grafer rettede grafer uden sløjfer eller flere kanter, det vil sige rettede grafer er rettede grafer uden sløjfer og multiple kanter, mens rettede grafer i den russiske oversættelse af bogen er rettet. grafer uden sløjfer og flere kanter. Dette fører til hyppig forvirring
  2. ↑ 1 2 BORODIN, IVANOVA, 2005 , s. 239.
  3. ↑ 1 2 Kostochka, Sopena, Zhu, 1997 , s. 331-340.
  4. ↑ BORODIN, IVANOVA, 2005 , s. 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