Orientált grafikon színezés

Az irányított gráfszínezés a gráfszínezés egy speciális fajtája . Mégpedig egy irányított gráf [1] csúcsaihoz színek hozzárendelése , amely

Egy másik definíció: A H digráf orientált k -színeződése a H * k - csúcsú digráf orientált homomorfizmusa [2] .

Orientált kromatikus szám

A G digráf orientált kromatikus száma az orientált színezéshez szükséges minimális színek száma. Ezt a számot általában jelölik . Ugyanez a definíció kiterjeszthető irányítatlan gráfokra is, ha egy irányítatlan gráf irányított kromatikus számát az összes orientációjának maximális kromatikus számaként definiáljuk [3] [2] .

Példák

Az 5 csúcsú orientált ciklus orientált kromatikus száma öt. Ha a ciklus négy vagy kevesebb színnel van színezve, akkor vagy két szomszédos csúcs színe lesz egyforma, vagy az egyiken át lévő két csúcs ugyanolyan színű lesz. Ez utóbbi esetben a két csúcsot a középső csúcsgal összekötő élek hibásan lesznek színezve (második szabály) - mindkét ívnek azonos színű végei vannak, de a színeket ellentétes irányban kötik össze. Így nem lehetséges négy vagy kevesebb színnel színezni. Ha az összes csúcsot különböző színűre színezzük, akkor egy megengedett orientált színezést kapunk.

Tulajdonságok

Orientált színezés csak hurkok és orientált 2 ciklus nélküli digráfoknál létezhet, mivel a hurok az ív mindkét végén egy színt ad, és a második szabály nem engedi meg a 2 ciklust – két szín ellentétes irányban kapcsolódik . Ha ezek a feltételek teljesülnek, mindig van orientált színezés, például ha minden csúcshoz más színt rendelünk.

Ha egy orientált színezés teljes , abban az értelemben, hogy nem lehet két színt összevonni ugyanabba a színbe a megfelelő színezés érdekében, akkor a színezés egyetlen versenyhomomorfizmusnak felel meg . A versenyen a színezés minden színéhez egy csúcs tartozik. Minden színpárnál van egy ív a színes gráfban, melynek végein ez a két szín található, ami megfelel a tornában a megfelelő színek csúcsai közötti él tájolásának. A hiányos színezéseket egy versenyhomomorfizmus is ábrázolhatja, de ebben az esetben a színezések és a homomorfizmusok közötti megfelelés nem egy az egyhez.

A korlátos nemzetség , korlátos fokszámú vagy korlátos aciklikus kromatikus számú irányítatlan gráfoknak is van korlátos irányított kromatikus száma [3] .

Az orientált kromatikus szám becslései

Egy gráf orientált kromatikus száma jelentősen eltérhet a (közönséges) kromatikus számától. Például vannak kétrészes gráfok tetszőlegesen nagy orientált kromatikus számmal, elegendő a gráf minden élét 2 hosszúságú útvonalra cserélni, majd a kapott gráfban minden ilyen útvonal végeit különböző színekre kell festeni. [4] .

Courcelle [5] bebizonyította, hogy bármilyen síkgráf esetében, Raspud és Soupina [6] pedig 80-ra javította az eredményt. Borodin és munkatársai a következő tételt publikálták [7] :

Tétel : Legyen G g síkgráfja , akkor
(1) (2) (3) (4)


Borodin [8] egy másik cikkében a tétel (1)-beli korlátozását 13-ra lazították.

Jegyzetek

  1. ↑ A cikkben az irányított gráf irányított gráfot jelent. Distel „Graph Theory” című könyvének angol nyelvű változatában az orientált gráfok hurok vagy több él nélküli irányított gráfok, vagyis az irányított gráfok hurok és több él nélküli irányított gráfok, míg a könyv orosz fordításában az irányított gráfok irányítottak. ciklusok és több él nélküli gráfok. Ez gyakori zavarokhoz vezet
  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, Nyugat, 2004 , pp. 147-159.

Irodalom