Orientované zbarvení - Oriented coloring

v teorie grafů, orientované zbarvení grafu je speciální typ zbarvení grafu. Jmenovitě jde o přiřazení barev k vrcholům orientovaný graf že

• je správně: žádné dva sousední vrcholy nedostanou stejnou barvu a
• je důsledně orientovaný: pokud vrcholy ${displaystyle u}$ a ${displaystyle u '}$ mají stejnou barvu a vrcholy ${displaystyle v}$ a ${displaystyle v '}$ mít tedy stejnou barvu ${displaystyle (u, v)}$ a ${displaystyle (v ', u')}$ nemohou být obě hrany v grafu.

Ekvivalentně, orientované zbarvení grafu grafu G je orientovaný graf H (jejichž vrcholy představují barvy a jejichž oblouky představují platné orientace mezi barvami) tak, že existuje a homomorfismus z G na H.

An orientované chromatické číslo grafu G je nejméně barev potřebných pro orientované vybarvení; obvykle se označuje ${displaystyle scriptstyle chi _ {o} (G)}$. Stejnou definici lze rozšířit i na neorientované grafy definováním orientovaného chromatického čísla neorientovaného grafu jako největšího orientovaného chromatického čísla kteréhokoli z jeho orientace.^[1]

Příklady

Orientované chromatické číslo směrovaného 5 cyklu je pět. Pokud je cyklus zbarven čtyřmi nebo méně barvami, pak buď dva sousední vrcholy mají stejnou barvu, nebo dva vrcholy vzdálené dva kroky mají stejnou barvu. V druhém případě jsou okraje spojující tyto dva vrcholy s vrcholem mezi nimi nekonzistentně orientovány: obě mají stejnou dvojici barev, ale s opačnou orientací. Není tedy možné žádné zbarvení čtyřmi nebo méně barvami. Pokud však každému vrcholu dáte svou vlastní jedinečnou barvu, dojde k platnému orientovanému zbarvení.

Vlastnosti

Orientované vybarvení může existovat pouze pro směrovaný graf bez smyček nebo směrovaných 2 cyklů. Protože smyčka nemůže mít na svých koncových bodech různé barvy a 2-cyklus nemůže mít obě své hrany konzistentně orientované mezi stejnými dvěma barvami. Pokud jsou tyto podmínky splněny, pak vždy existuje orientované zbarvení, například zbarvení, které každému vrcholu přiřadí jinou barvu.

Pokud je orientované zbarvení kompletní, v tom smyslu, že žádné dvě barvy nelze sloučit, aby vzniklo zbarvení s menším počtem barev, pak jednoznačně odpovídá a homomorfismus grafů do turnaj. Turnaj má jeden vrchol pro každou barvu v barvení. Pro každou dvojici barev je v barevném grafu hrana s těmito dvěma barvami v jejích koncových bodech, která propůjčuje její orientaci hraně v turnaji mezi vrcholy odpovídajícími dvěma barvám. Neúplná zbarvení mohou být také reprezentována homomorfismy do turnajů, ale v tomto případě není korespondence mezi barvením a homomorfismem jedna k jedné.

Neusměrněné grafy ohraničené rod, ohraničený stupeň nebo ohraničené acyklické chromatické číslo také mají ohraničené orientované chromatické číslo.^[1]

Viz také

• Sopena napsala průzkumnou práci o orientovaném barvení grafů.^[2]
• Stránka Oriented Coloring (udržuje Sopena)

Reference