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:
- 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ä :
- χ″( G ) = Δ( G ) + 1 ellei G = K 2 [11]
- Δ( G ) ≤ 2 8( G ). [yksitoista]
- Δ( G ) ≤ n/2 + 1. [12]
Tässä χ″( G ) on kromaattinen kokonaisluku ; Δ( G ) on maksimiaste ja δ( G ) on minimiaste.
Muistiinpanot
- ↑ 12 Fowler , 1998 .
- ↑ Truszczyński, 1984 .
- ↑ Xu, 1990 .
- ↑ Wilson, 1976 .
- ↑ Thomason, 1978 .
- ↑ 1 2 Belcastro, Haas, 2015 .
- ↑ Tutte, 1976 .
- ↑ Bollobás, 1978 .
- ↑ Schwenk, 1989 .
- ↑ Mahmoodian, Shokrollahi, 1995 .
- ↑ 1 2 Akbari, Behzad, Hajiabolhassan, Mahmoodian, 1997 .
- ↑ Akbari, 2003 .
Kirjallisuus
- S. Akbari. Kaksi arvelua ainutlaatuisesti täysin väritettävistä kaavioista // Discrete Mathematics . - 2003. - T. 266 , no. 1-3 . - S. 41-45 . - doi : 10.1016/S0012-365X(02)00797-5 .
- S. Akbari, M. Behzad, H. Hajiabolhassan, E. S. Mahmoodian. Ainutlaatuiset värilliset kaaviot // Grafit ja kombinatoriikka . - 1997. - T. 13 , no. 4 . — S. 305–314 . - doi : 10.1016/S0012-365X(02)00797-5 .
- Sarah-Marie Belcastro, Ruth Haas. Kolmioton, ainutlaatuisesti 3-reunaiset väritettävät kuutiokaaviot // Discrete Mathematics. - 2015. - T. 10 , nro 2 . — s. 39–44 . - arXiv : 1508.06934 .
- Bela Bollobas. Extreme Graph Theory. - Academic Press, 1978. - Vol. 11. - (LMS Monographs).
- Thomas Fowler. Tasokaavioiden ainutlaatuinen väritys. — Georgia Institute of Technologyn matematiikan osasto, 1998.
- Christopher J. Hillar, Troels Windfeldt. Yksilöllisesti kärkipisteiden värittävien graafien algebrallinen karakterisointi // Journal of Combinatorial Theory . - 2008. - T. 98 , no. 2 . — S. 400–414 . - doi : 10.1016/j.jctb.2007.08.004 .
- ES Mahmoodian, MA Shokrollahi. Combinatoriics Advances. — Dordrecht; Boston; Lontoo: Kluwer Academic Publishers, 1995, osa 329, s. 321–324. - (Matematiikka ja sen sovellukset).
- Allen J. Schwenk. Hamiltonin syklien luettelointi tietyissä yleistetyissä Petersen-kaavioissa // Journal of Combinatorial Theory . - 1989. - T. 47 , no. 1 . — s. 53–59 . - doi : 10.1016/0095-8956(89)90064-6 .
- A.G. Thomason. Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). - 1978. - T. 3. - S. 259-268. — (Diskreetin matematiikan vuosikirjat).
- M. Truszczyński. Äärelliset ja äärettömät joukot. Voi. I, II. Egerissä 6.–11. heinäkuuta 1981 pidetyn kuudennen unkarilaisen kombinatorisen kollokvion julkaisuja / András Hajnal, László Lovász, Vera T. Sós. - Pohjois-Hollanti, Amsterdam, 1984. - T. 37. - S. 733-748. - (Keskustelu. Math. Soc. Janos Bolyai).
- William T Tutte. Colloquio Internazionale sulle Teorie Combinatorie (Rooma, 1973), Tomo I. - Accad. Naz. Lincei, Rooma, 1976, s. 193–199. Atti dei Convegni Lincei, No. 17. . Kuten siteerataan julkaisuissa Belcastro ja Haas ( Belcastro, Haas 2015 ).
- Shao Ji Xu. Yksilöllisesti väritettävien kaavioiden koko // Journal of Combinatorial Theory . - 1990. - T. 50 , no. 2 . — S. 319–320 . - doi : 10.1016/0095-8956(90)90086-F .
- RJ Wilson. Proc. British Comb. Conf. 1975. - Winnipeg: Utilitas Math., 1976. - S. 696. . Kuten mainitaan julkaisussa Thomason ( Thomason 1978 ).
Linkit