Colorare grafică orientată

Colorarea grafică direcționată este un tip special de colorare a graficului . Și anume, este alocarea de culori la vârfurile unui graf direcționat [1] , care

O altă definiție: O k -colorare orientată a unui digraf H este un homomorfism orientat la un k -vertex digraf H* [2] .

Număr cromatic orientat

Numărul cromatic orientat al unui digraf G este numărul minim de culori necesare într-o colorare orientată. Acest număr este de obicei notat ca . Aceeași definiție poate fi extinsă la grafurile nedirecționate prin definirea numărului cromatic direcționat al unui graf nedirecționat ca număr cromatic maxim al tuturor orientărilor sale [3] [2] .

Exemple

Numărul cromatic orientat al unui ciclu orientat cu 5 vârfuri este cinci. Dacă ciclul este colorat cu patru sau mai puține culori, atunci fie două vârfuri adiacente vor fi colorate la fel, fie două vârfuri printr-unul vor avea aceeași culoare. În acest din urmă caz, marginile care leagă aceste două vârfuri cu vârful din mijloc vor fi colorate incorect (a doua regulă) - ambele arce au capete de aceeași culoare, dar conectează culorile în direcția opusă. Astfel, nu este posibilă nicio colorare cu patru sau mai puține culori. Dacă colorăm toate vârfurile în culori diferite, obținem o colorare orientată admisibilă.

Proprietăți

O colorare orientată poate exista doar pentru digrafele fără bucle și fără 2-cicluri orientate, deoarece o buclă dă o culoare la ambele capete ale unui arc, iar un ciclu de 2 nu este permis de a doua regulă - două culori sunt conectate în direcții opuse . Dacă aceste condiții sunt îndeplinite, există întotdeauna o colorare orientată, de exemplu, dacă atribuim culori diferite tuturor nodurilor.

Dacă o colorare orientată este completă , în sensul că două culori nu pot fi îmbinate în aceeași culoare pentru a da o colorare adecvată, atunci colorarea corespunde unui singur homomorfism de turneu . Turneul are câte un vârf pentru fiecare culoare din colorare. Pentru fiecare pereche de culori, există un arc în graficul colorat cu aceste două culori la capete, care corespunde orientării muchiei în turneu între vârfurile culorilor corespunzătoare. Colorațiile incomplete pot fi reprezentate și printr-un homomorfism de turneu, dar în acest caz corespondența dintre colorații și homomorfisme nu este unul la unu.

Graficele nedirecționate cu gen mărginit, grad mărginit sau număr cromatic aciclic mărginit au și număr cromatic direcționat mărginit [3] .

Estimări pentru numărul cromatic orientat

Numărul cromatic orientat al unui grafic poate diferi semnificativ de numărul său cromatic (obișnuit). De exemplu, există grafice bipartite cu un număr cromatic orientat în mod arbitrar mare, este suficient să înlocuiți fiecare margine a graficului cu o cale de lungime 2, iar apoi capetele fiecărei astfel de căi din graficul rezultat trebuie pictate în culori diferite. [4] .

Courcelle [5] a demonstrat că pentru orice graf planar, iar Raspud și Soupina [6] au îmbunătățit rezultatul la 80. Borodin și colab. au publicat următoarea teoremă [7] :

Teorema : Fie G un grafic plan al lui g , apoi
(1) (2) (3) (4)


Într-un alt articol al lui Borodin [8] , restricția din (1) a teoremei a fost relaxată la 13.

Note

  1. ↑ În articol, un grafic direcționat înseamnă un grafic direcționat. În versiunea în limba engleză a cărții lui Distel „Teoria graficelor”, graficele orientate sunt grafice direcționate fără bucle sau margini multiple, adică graficele direcționate sunt grafice direcționate fără bucle și margini multiple, în timp ce în traducerea rusă a cărții, graficele direcționate sunt direcționate. grafice fără bucle și margini multiple. Acest lucru duce la confuzii frecvente
  2. ↑ 1 2 BORODIN, IVANOVA, 2005 , p. 239.
  3. ↑ 1 2 Kostochka, Sopena, Zhu, 1997 , p. 331–340.
  4. ↑ BORODIN, IVANOVA, 2005 , p. 240.
  5. ↑ Courselle, 1994 .
  6. ↑ Raspaud, Sopena, 1994 , pp. 171-174.
  7. ↑ Borodin, Kostochka, Nešetřil, Raspaud, Sopena, 1999 , pp. 77-90.
  8. ↑ Borodin, Kim, Kostochka, Vest, 2004 , pp. 147-159.

Literatură