Hvatala gróf

Hvatala gróf

Valaki után elnevezve	Václav Chvatal
Csúcsok	12
borda	24
Sugár	2
Átmérő	2
Heveder	négy
Automorfizmusok	8 ( D4 )
Kromatikus szám	négy
Kromatikus index	négy
Tulajdonságok	euler hamiltoni szabályos háromszögek nélkül
Médiafájlok a Wikimedia Commons oldalon

A Chvatala gráf egy 12 csúcsból és 24 élből álló irányítatlan gráf, amelyet Vaclav Chvatala fedezett fel 1970 -ben.

Tulajdonságok

A grafikon nem tartalmaz háromszögeket - kerülete (a legkisebb ciklus hossza) négy. A gráf 4 - szabályos - minden csúcsnak pontosan négy szomszédja van. A grafikon kromatikus száma 4 - négy színnel lehet színezni, de hárommal nem. Ahogy Chwatal felfedezte, ez egy minimális, 4 színű, 4 szabályos háromszög nélküli gráf. Egy kisebb, háromszög nélküli, 4 színű gráf a Grötzsch-gráf , amelynek 11 csúcsa van, de maximum 5 foka van, és nem szabályos.

A gráf nem csúcstranzitív – az automorfizmus-csoportnak csak egy 8-as és egy 4-es csúcspályája van.

Brooks tétele szerint bármely szabályos gráfnak (kivéve a páratlan ciklusokat és a klikkeket) a kromatikus száma nem haladja meg a . Illetve Erdősnek köszönhetően 1959 óta köztudott, hogy mindenre és létezik - színes, kerületi grafikon . E két eredmény és néhány példa, köztük a Chwatala-gráf alapján Branko Grünbaum 1970-ben azt sejtette, hogy bármely és létezik egy -színes - reguláris gráf körmérettel . A Chvatala gráf erre a sejtésre ad megoldást a = = 4 esetre. Grünbaum sejtését kellően nagyra cáfolta Johansen [1] , aki kimutatta, hogy a háromszög nélküli gráfok kromatikus száma , ahol a csúcsok maximális foka, és azt jelenti , hogy az "O" nagy . Ennek a cáfolatnak a ellenére továbbra is érdekes probléma marad példákat találni kis értékkel és nagy kerülettel rendelkező -színezett - szabályos grafikonokra. $k$ $k$ $k$ $l$ $k$ $l$ $k$ $l$ $k$ $k$ $l$ $k$ $l$ $k$ $O(\Delta /\log \Delta )$ $\Delta$ $O$ $k$ $k$ $k$

Bruce Reid alternatív sejtése [1] azt állítja, hogy a háromszög nélküli, magas csúcsfokozatú gráfok kromatikus számának lényegesen kisebbnek kell lennie, mint a fokszámnak, és általánosabban, a maximális fokszámú és maximális méretű klikkel rendelkező gráfoknak kromatikus számmal kell rendelkezniük: $\Delta$ $\omega$

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

Ennek a sejtésnek az esete kellően nagyokhoz következik Johansen eredményéből. A Chvatala gráf azt mutatja, hogy Reid sejtésénél a felfelé kerekítés elengedhetetlen, mivel a Chvatala gráf esetében ez kisebb, mint a kromatikus szám, de felfelé kerekítéskor egyenlővé válik vele. $\omega =2$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

A gráfgraft Hamilton -féle, és kulcsszerepet játszik Fleischner és Sabidoussi [2] bizonyításában , miszerint annak ellenőrzése, hogy egy háromszög nélküli Hamilton-gráf háromszínű-e, NP-teljes probléma .

A Chvatala gráf karakterisztikus polinomja egyenlő . A Chwatala -gráf Tatta-polinomját 2008-ban számították ki [3] . ${\megjelenítési stílus (x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)}$

A gráf függetlenségi száma 4.

Galéria

A Chvatal gróf kromatikus száma 4.
A Chwatal-gráf kromatikus indexe 4.
A gróf megragadta a Hamiltonokat .
Khvatala gróf alternatív rajza.

Irodalom

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: A 2008-as, 49. éves IEEE szimpózium a számítástechnika alapjairól szóló anyaga. – Washington, DC, USA: IEEE Computer Society, 2008. – 677–686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 . .
V. Chvatal. A legkisebb háromszög nélküli 4-kromatikus 4-reguláris gráf // Journal of Combinatorial Theory. - 1970. - T. 9 , sz. 1 . – S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Erds Pál. Gráfelmélet és valószínűség // Canadian Journal of Mathematics. - 1959. - T. 11 . – S. 34–38 . - doi : 10.4153/CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. 4-reguláris Hamilton-gráfok 3-színezhetősége // Journal of Graph Theory. - 2002. - T. 42 , sz. 2 . – S. 125–140 . - doi : 10.1002/jgt.10079 . .
B. Grunbaum. Probléma a grafikonok színezésében // American Mathematical Monthly. - Mathematical Association of America, 1970. - V. 77 , no. 10 . – S. 1088–1092 . - doi : 10.2307/2316101 . — . .
nád. ω, Δ és χ // Journal of Graph Theory. - 1998. - T. 27 , sz. 4 . – S. 177–212 . - doi : 10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K . .

Linkek

Weisstein, Eric W. Chvátal Graph (angol) a Wolfram MathWorld weboldalán .