Orientoitu graafin väritys

Suunnattu graafin väritys on erityinen graafin värjäys . Se on nimittäin värien osoittamista suunnatun graafin [1] kärkipisteille , mikä

Toinen määritelmä: Digraafin H orientoitu k -väritys on orientoitu homomorfismi k -kärkipisteen digraafiin H* [2] .

Orientoitu kromaattinen numero

Digraafin G orientoitu kromaattinen luku on suuntautetun värityksen edellyttämä värien vähimmäismäärä. Tämä numero on yleensä merkitty . Sama määritelmä voidaan laajentaa suuntaamattomiin graafisiin määrittämällä suuntaamattoman graafin suunnattu kromaattinen luku kaikkien sen orientaatioiden maksimikromaattiseksi lukumääräksi [3] [2] .

Esimerkkejä

Orientoidun syklin, jossa on 5 kärkeä, orientoitu kromaattinen luku on viisi. Jos sykli on värjätty neljällä tai vähemmällä värillä, joko kaksi vierekkäistä kärkeä värjätään samalla tavalla tai kahdella yhden pisteen välillä on sama väri. Jälkimmäisessä tapauksessa reunat, jotka yhdistävät nämä kaksi kärkeä keskellä olevaan kärkeen, väritetään väärin (toinen sääntö) - molemmilla kaarilla on samat värilliset päät, mutta yhdistävät värit vastakkaiseen suuntaan. Näin ollen neljällä tai vähemmällä värillä värjäys ei ole mahdollista. Jos värjäämme kaikki kärjet eri väreillä, saamme hyväksyttävän orientoidun värityksen.

Ominaisuudet

Suunnattu väritys voi olla olemassa vain digrafeille, joissa ei ole silmukoita ja ilman suunnattuja 2-jaksoja, koska silmukka antaa yhden värin kaaren molemmissa päissä, ja 2-sykliä ei sallita toinen sääntö – kaksi väriä on kytketty vastakkaisiin suuntiin. . Jos nämä ehdot täyttyvät, on aina olemassa suuntautunut väritys, esimerkiksi jos annamme eri värit kaikille vertekseille.

Jos suunnattu väritys on täydellinen siinä mielessä, että kahta väriä ei voida yhdistää samaan väriin oikean värin saamiseksi, väritys vastaa yhtä turnauksen homomorfismia . Turnauksessa on yksi kärki jokaiselle värityksen värille. Jokaiselle väriparille on värillisessä kaaviossa kaari, jonka päissä on nämä kaksi väriä, mikä vastaa turnauksen reunan suuntausta vastaavien värien kärkien välillä. Epätäydellisiä värjäyksiä voidaan esittää myös turnaushomomorfismilla, mutta tässä tapauksessa väritysten ja homomorfismien välinen vastaavuus ei ole yksi yhteen.

Suuntamattomilla graafeilla, joissa on rajoitettu suku , rajattu aste tai rajoitettu asyklinen kromaattinen luku , on myös rajoitettu suunnattu kromaattinen luku [3] .

Orientoidun kromaattisen luvun arviot

Graafin orientoitu kromaattinen luku voi poiketa merkittävästi sen (tavallisesta) kromaattisesta numerosta. Esimerkiksi on olemassa kaksiosaisia ​​grafiikoita, joissa on mielivaltaisen suuri orientoitu kromaattinen luku, riittää, että graafin jokainen reuna korvataan polulla, jonka pituus on 2, ja sitten jokaisen sellaisen polun päät tuloksena olevassa graafissa on maalattava eri väreillä. [4] .

Courcelle [5] osoitti, että millä tahansa tasograafilla, ja Raspud ja Soupina [6] paransivat tuloksen 80:een. Borodin ym. julkaisivat seuraavan lauseen [7] :

Lause : Olkoon G g : n tasograafi , sitten
(1) (2) (3) (4)


Toisessa Borodinin [8] artikkelissa lauseen (1) rajoitus lievennettiin arvoon 13.

Muistiinpanot

  1. ↑ Artikkelissa suunnattu graafi tarkoittaa suunnattua graafia. Distelin kirjan "Graph Theory" englanninkielisessä versiossa orientoidut graafit ovat suunnattuja graafeja ilman silmukoita tai useita reunoja, eli suunnatut graafit ovat suunnattuja graafeja ilman silmukoita ja useita reunoja, kun taas kirjan venäjänkielisessä käännöksessä suunnatut graafit ovat suunnattuja. graafit ilman silmukoita ja useita reunoja. Tämä johtaa usein sekaannukseen
  2. ↑ 1 2 BORODIN, IVANOVA, 2005 , s. 239.
  3. ↑ 1 2 Kostochka, Sopena, Zhu, 1997 , s. 331-340.
  4. ↑ BORODIN, IVANOVA, 2005 , s. 240.
  5. ↑ Courselle, 1994 .
  6. ↑ Raspaud, Sopena, 1994 , s. 171-174.
  7. ↑ Borodin, Kostochka, Nešetřil, Raspaud, Sopena, 1999 , s. 77-90.
  8. ↑ Borodin, Kim, Kostochka, West, 2004 , s. 147-159.

Kirjallisuus