Orientované zbarvení grafu

Orientované zbarvení grafu je speciální druh zbarvení grafu . Jmenovitě jde o přiřazení barev k vrcholům orientovaného grafu [1] , který

Jiná definice: Orientované k -zabarvení digrafu H je orientovaný homomorfismus ke k -vertexovému digrafu H* [2] .

Orientované chromatické číslo

Orientované chromatické číslo digrafu G je minimální počet barev požadovaný pro orientované zbarvení. Toto číslo se obvykle označuje jako . Stejnou definici lze rozšířit i na neorientované grafy tím, že definujeme směrované chromatické číslo neorientovaného grafu jako maximální chromatické číslo všech jeho orientací [3] [2] .

Příklady

Orientované chromatické číslo orientovaného cyklu s 5 vrcholy je pět. Pokud je cyklus obarven čtyřmi nebo méně barvami, pak buď dva sousední vrcholy budou obarveny stejně, nebo dva vrcholy přes jeden budou mít stejnou barvu. V druhém případě budou hrany spojující tyto dva vrcholy s vrcholem uprostřed nesprávně obarveny (druhé pravidlo) - oba oblouky mají stejně barevné konce, ale spojují barvy v opačném směru. Není tedy možné žádné barvení čtyřmi nebo méně barvami. Pokud vybarvíme všechny vrcholy různými barvami, dostaneme přípustné orientované zbarvení.

Vlastnosti

Orientované zbarvení může existovat pouze pro digrafy bez smyček a bez orientovaných 2-cyklů, protože smyčka dává jednu barvu na obou koncích oblouku a 2-cyklus není povolen podle druhého pravidla – dvě barvy jsou spojeny v opačných směrech. . Pokud jsou tyto podmínky splněny, dochází vždy k orientovanému zbarvení, např. pokud všem vrcholům přiřadíme různé barvy.

Pokud je orientované zbarvení úplné , v tom smyslu, že žádné dvě barvy nemohou být sloučeny do stejné barvy, aby poskytly správné zbarvení, pak zbarvení odpovídá jedinému turnajovému homomorfismu . Turnaj má jeden vrchol pro každou barvu v zbarvení. Pro každou dvojici barev je v barevném grafu s těmito dvěma barvami na koncích oblouk, který odpovídá orientaci hrany v turnaji mezi vrcholy odpovídajících barev. Neúplná zbarvení mohou být také reprezentována turnejovým homomorfismem, ale v tomto případě není korespondence mezi zbarveními a homomorfismy jedna ku jedné.

Neorientované grafy s ohraničeným rodem , ohraničeným stupněm nebo ohraničeným acyklickým chromatickým číslem mají také ohraničené směrované chromatické číslo [3] .

Odhady pro orientované chromatické číslo

Orientované chromatické číslo grafu se může výrazně lišit od jeho (obyčejného) chromatického čísla. Například existují bipartitní grafy s libovolně velkým orientovaným chromatickým číslem, stačí každý okraj grafu nahradit cestou délky 2 a pak je třeba konce každé takové cesty ve výsledném grafu vybarvit různými barvami. [4] .

Courcelle [5] dokázal, že pro jakýkoli rovinný graf, a Raspud a Soupina [6] zlepšili výsledek na 80. Borodin et al publikovali následující větu [7] :

Věta : Nechť G je rovinný graf g , pak
(1) (2) (3) (4)


V jiném článku Borodina [8] bylo omezení v (1) věty uvolněno na 13.

Poznámky

  1. ↑ V článku znamená orientovaný graf orientovaný graf. V anglické verzi Distelovy knihy „Graph Theory“ jsou orientované grafy orientované grafy bez smyček nebo více hran, to znamená, že orientované grafy jsou orientované grafy bez smyček a více hran, zatímco v ruském překladu knihy jsou orientované grafy orientované grafy bez smyček a více hran. To vede k častým nejasnostem
  2. ↑ 1 2 BORODIN, IVANOVA, 2005 , str. 239.
  3. ↑ 1 2 Kostochka, Sopena, Zhu, 1997 , str. 331–340.
  4. ↑ BORODIN, IVANOVA, 2005 , str. 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, West, 2004 , pp. 147-159.

Literatura