Kreivi Hvatala

Kreivi Hvatala

Nimetty	Vaclav Chvatal
Huiput	12
kylkiluut	24
Säde	2
Halkaisija	2
Ympärysmitta	neljä
Automorfismit	8 ( D4 )
Kromaattinen numero	neljä
Kromaattinen indeksi	neljä
Ominaisuudet	euler hamiltonin säännöllinen ilman kolmioita
Mediatiedostot Wikimedia Commonsissa

Graafi Chvatala on ohjaamaton graafi , jossa on 12 kärkeä ja 24 reunaa , jonka Vaclav Chvatala löysi vuonna 1970.

Ominaisuudet

Kaavio ei sisällä kolmioita - sen ympärysmitta (pienimmän syklin pituus) on neljä. Kaavio on 4 - säännöllinen - jokaisella kärjellä on täsmälleen neljä naapuria. Kuvaajan kromaattinen luku on 4 - se voidaan värjätä neljällä värillä, mutta ei kolmella. Kuten Chwatal havaitsi, tämä on minimaalinen 4-värinen 4-säännöllinen kolmioton kaavio. Pienempi kolmioton 4-värinen graafi on Grötzsch-graafi , jossa on 11 kärkeä, mutta sen maksimiaste on 5 ja se ei ole säännöllinen.

Graafi ei ole kärkitransitiivinen - automorfismiryhmässä on vain yksi kärkikiertorata, jonka pituus on 8 ja yksi pituus 4.

Brooksin lauseen mukaan minkä tahansa säännöllisen graafin (paitsi parittomat jaksot ja klikkit) kromaattinen luku on enintään . Lisäksi Erdősin ansiosta vuodesta 1959 lähtien on tiedetty, että kaikille on olemassa värillisiä kaavioita, joissa on ympärysmitta . Näiden kahden tuloksen ja joidenkin esimerkkien, mukaan lukien Chwatala-graafin, perusteella Branko Grünbaum arveli vuonna 1970, että mille tahansa ja on olemassa -värinen -säännöllinen graafi, jonka ympärysmitta on . Chvatala-graafi antaa ratkaisun tähän olettamukseen tapauksessa = = 4. Johansen [1] kumosi Grünbaumin olettamuksen riittävän suurelta ja osoitti, että graafien kromaattinen lukumäärä ilman kolmioita on , missä on pisteiden maksimiaste ja tarkoittaa "O" on suuri . Tästä kiistämisestä huolimatta on edelleen mielenkiintoinen ongelma löytää esimerkkejä -värisistä -säännöllisistä kaavioista, joissa on pienet arvot ja suuri ympärysmitta. $k$ $k$ $k$ $l$ $k$ $l$ $k$ $l$ $k$ $k$ $l$ $k$ $l$ $k$ $O(\Delta /\log \Delta )$ $\Delta$ $O$ $k$ $k$ $k$

Bruce Reidin vaihtoehtoinen olettamus [1] sanoo, että kolmiottomilla graafilla, jolla on korkea kärkiaste, tulisi olla huomattavasti pienempi kromaattinen luku kuin aste, ja yleisemmin, että graafilla, jolla on maksimiaste ja maksimikoko , tulisi olla kromaattinen luku: $\Delta$ $\omega$

\chi (G)\leqslant \left\lceil {\frac {\Delta +\omega +1}{2))\right\rceil

Tämän olettamuksen tapaus seuraa riittävän suurille Johansenin tuloksesta. Chvatala-graafi osoittaa, että pyöristäminen ylöspäin Reidin olettamuksessa on olennaista, koska Chvatala-graafissa , joka on pienempi kuin kromaattinen luku, mutta tulee sen suuruiseksi pyöristettäessä ylöspäin. $\omega =2$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

Graafigrafti on Hamiltonin ja sillä on keskeinen rooli Fleischnerin ja Sabidoussin [2] todistuksessa , jonka mukaan kolmiotonta Hamiltonin graafin kolmivärisyyden tarkistaminen on NP-täydellinen ongelma .

Chvatala-graafin ominaispolynomi on yhtä suuri kuin . Chwatala-graafin Tatta- polynomi laskettiin vuonna 2008 [3] . ${\näyttötyyli (x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)}$

Graafin riippumattomuusluku on 4.

Galleria

Chvatalin kromaattinen luku on 4.
Chwatal-graafin kromaattinen indeksi on 4.
Kreivi nappasi Hamiltonit .
Vaihtoehtoinen piirros kreivi Khvatalasta.

Kirjallisuus

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: Vuoden 2008 49. vuotuisen tietojenkäsittelytieteen perusteita käsittelevän IEEE-symposiumin julkaisuja. — Washington, DC, USA: IEEE Computer Society, 2008. — s. 677–686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 . .
V. Chvatal. Pienin kolmioton 4-kromaattinen 4-säännöllinen graafi // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 1 . — S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Paul Erds. Graafiteoria ja todennäköisyys // Canadian Journal of Mathematics. - 1959. - T. 11 . — S. 34–38 . - doi : 10.4153/CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. 4-säännöllisten Hamiltonin graafien kolmivärisyys // Journal of Graph Theory. - 2002. - T. 42 , no. 2 . — S. 125–140 . - doi : 10.1002/jgt.10079 . .
B. Grunbaum. Ongelma kaavioiden värjäyksessä // American Mathematical Monthly. - Mathematical Association of America, 1970. - V. 77 , no. 10 . — S. 1088–1092 . - doi : 10.2307/2316101 . — . .
ruoko. ω, Δ ja χ // Journal of Graph Theory. - 1998. - T. 27 , no. 4 . — S. 177–212 . - doi : 10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K . .

Linkit

Weisstein, Eric W. Chvátal Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .