Ainutlaatuisen värikäs kaavio

Yksilöllisesti väritettävä graafi on k-värinen graafi, joka sallii vain yhden (oikean) k -värityksen (värien permutaatioon asti).

Esimerkkejä

Täydellinen kaavio on yksilöllisesti väritettävissä, koska siinä on vain yksi kelvollinen väritys - jokaiselle kärjelle on määritetty eri väri.

Mikä tahansa k - puu on yksilöllisesti väritettävissä ( k  + 1) väreillä. Tasograafit , jotka ovat yksiselitteisesti väritettävissä 4 värillä , ovat täsmälleen Apollonius-kaavioita , eli tasomaisia ​​3-puita [1] .

Ominaisuudet

Joitakin ainutlaatuisesti k -värittävän graafin G ominaisuuksia, jossa on n kärkeä ja m reunaa:

  1. m ≥ ( k - 1) n - k ( k -1)/2 [2] [3]

Aiheeseen liittyvät käsitteet

Minimaalinen epätäydellisyys

Minimaalisesti epätäydellinen graafi on graafi, jossa jokainen aligraafi on täydellinen . Huippupisteiden poistaminen minimaalisen epätäydellisestä graafista jättää ainutlaatuisen väritetyn aligraafin.

Yksiarvoinen reunavärjäys

Yksilöllisesti viivavärjättävä graafi on k - reuna -värinen graafi , joka sallii vain yhden (oikean) k -reunavärjäyksen värien permutaatioon asti. Vain polut ja syklit sallivat yksiarvoisen 2-reunavärjäyksen. Millä tahansa k :n arvolla tähdet K 1, k ovat yksiselitteisesti k - reunaväritettäviä kuvaajia. Wilson [4] esitti kuitenkin oletuksen, ja Thomason [5] osoitti, että k ≥ 4:lle nämä ovat tämän perheen ainoat jäsenet. On kuitenkin ainutlaatuisia 3-reunaisia ​​väritettäviä kaavioita, jotka eivät kuulu tähän luokitukseen, kuten kolmiopyramidikaavio .

Jos kuutiograafi on yksiselitteisesti 3-reunaväritettävä, siinä on oltava täsmälleen kolme Hamiltonin sykliä , jotka muodostuvat kahden (kolmesta) värin reunoista, mutta joillakin kuutiograafilla, jossa on vain kolme Hamiltonin sykliä, ei ole ainutlaatuista 3-reunavärjäystä. [6] . Mikä tahansa yksinkertainen tasomainen kuutiograafi, joka sallii ainutlaatuisen 3-reunavärjäyksen, sisältää kolmion [1] , mutta Tut [7] huomasi, että yleistetty Petersen-graafi G (9,2) on ei- tasomainen kolmioton graafi, mutta se on ainutlaatuisesti 3-reunaväritettävä. Monien vuosien ajan tämä graafi oli ainoa esimerkki tällaisista kaavioista (katso Bolobashin [8] ja Schwenkin [9] artikkelit ), mutta nyt on olemassa äärettömän paljon ei-tasomaisia ​​kolmioita sisältäviä kuutiokaavioita, joissa on yksiarvoinen 3-reuna. -värjäys [6] .

Yksi-yhteen täysi väritys

Ainutlaatuisen täysin värittävissä oleva graafi on täysin k - värinen graafi , joka sallii vain yhden (oikean) k -värityksen (värien permutaatioon asti).

Tyhjät graafit , polut ja syklit , joiden pituus on jaollinen kolmella, ovat yksilöllisesti täysin väritettäviä kaavioita. Mahmudian ja Shokrollahi [10] arvelivat , että vain nämä kaaviot muodostavat perheen.

Joitakin ainutlaatuisen täysin k -värjättävän graafin G ominaisuuksia, jossa on n kärkeä :

  1. χ″( G ) = Δ( G ) + 1 ellei G = K 2 [11]
  2. Δ( G ) ≤ 2 8( G ). [yksitoista]
  3. Δ( G ) ≤ n/2 + 1. [12]

Tässä χ″( G ) on kromaattinen kokonaisluku ; Δ( G ) on maksimiaste ja δ( G ) on minimiaste.

Muistiinpanot

  1. ↑ 12 Fowler , 1998 .
  2. ↑ Truszczyński, 1984 .
  3. ↑ Xu, 1990 .
  4. ↑ Wilson, 1976 .
  5. ↑ Thomason, 1978 .
  6. ↑ 1 2 Belcastro, Haas, 2015 .
  7. ↑ Tutte, 1976 .
  8. ↑ Bollobás, 1978 .
  9. ↑ Schwenk, 1989 .
  10. ↑ Mahmoodian, Shokrollahi, 1995 .
  11. ↑ 1 2 Akbari, Behzad, Hajiabolhassan, Mahmoodian, 1997 .
  12. ↑ Akbari, 2003 .

Kirjallisuus

Linkit