Orienterad färgsättning

Inom grafteorin är orienterad graffärgning en speciell typ av graffärgning . Det är nämligen en tilldelning av färger till hörn av en orienterad graf som

• är korrekt : inga två angränsande hörn får samma färg, och
• är konsekvent orienterad : om hörn $u$ och $u'$ har samma färg, och hörn $v$ och $v'$ har samma färg, då $(u,v)$ och $(v',u')$ kan inte båda vara kanter i grafen.

På motsvarande sätt är en orienterad graffärgning av en graf G en orienterad graf H (vars hörn representerar färger och vars bågar representerar giltiga orienteringar mellan färger) så att det finns en homomorfism från G till H .

Ett orienterat kromatiskt tal för en graf G är det minsta antalet färger som behövs i en orienterad färgsättning; det betecknas vanligtvis med $\scriptstyle \chi _{o}(G)$ . Samma definition kan utökas till oriktade grafer också genom att definiera det orienterade kromatiska numret för en oriktat diagram till att vara det största orienterade kromatiska numret av någon av dess orienteringar .

Exempel

Det orienterade kromatiska talet för en riktad 5-cykel är fem. Om cykeln är färgad av fyra eller färre färger, har antingen två intilliggande hörn samma färg, eller två hörn med två steg ifrån varandra har samma färg. I det senare fallet är kanterna som förbinder dessa två hörn med vertexet mellan dem inkonsekvent orienterade: båda har samma färgpar men med motsatt orientering. Således är ingen färgläggning med fyra eller färre färger möjlig. Men att ge varje vertex sin egen unika färg leder till en giltig orienterad färgning.

Egenskaper

En orienterad färgning kan endast existera för en riktad graf utan slingor eller riktade 2-cykler. För, en slinga kan inte ha olika färger vid sina ändpunkter, och en 2-cykel kan inte ha båda sina kanter konsekvent orienterade mellan samma två färger. Om dessa villkor är uppfyllda, så finns det alltid en orienterad färgning, till exempel färgen som tilldelar en annan färg till varje vertex.

Om en orienterad färgläggning är komplett , i den meningen att inga två färger kan slås samman för att producera en färg med färre färger, så motsvarar den unikt en grafhomomorfism till en turnering . Turneringen har ett hörn för varje färg i färgen. För varje färgpar finns det en kant i den färgade grafen med de två färgerna vid sina ändpunkter, vilket ger dess orientering till kanten i turneringen mellan de hörn som motsvarar de två färgerna. Ofullständiga färger kan också representeras av homomorfismer i turneringar, men i detta fall är överensstämmelsen mellan färgningar och homomorfismer inte en-till-en.

Oriktade grafer av avgränsat släkte , avgränsad grad eller avgränsat acykliskt kromatiskt tal har också ett begränsat orienterat kromatiskt tal.

Se även

• Sopena skrev en enkätrapport om orienterad graffärgning.
• Den orienterade målarboken (underhålls av Sopena)