Greve Hvatala

Greve Hvatala

Döpt efter	Vaclav Chvatal
Toppar	12
revben	24
Radie	2
Diameter	2
Omkrets	fyra
Automorfismer	8 ( D4 )
Kromatiskt nummer	fyra
Kromatiskt index	fyra
Egenskaper	euler hamiltonian regelbunden utan trianglar
Mediafiler på Wikimedia Commons

Graf Chvatala är en oriktad graf med 12 hörn och 24 kanter som upptäcktes av Vaclav Chvatala 1970.

Egenskaper

Grafen innehåller inga trianglar - dess omkrets (längden på den minsta cykeln) är lika med fyra. Grafen är 4 - regelbunden - varje vertex har exakt fyra grannar. Grafens kromatiska nummer är 4 - den kan färgas med fyra färger, men inte med tre. Som Chwatal upptäckte är detta en graf med minimal 4-färgs 4-regelbunden triangelfri graf. En mindre triangelfri 4-färgsgraf är Grötzsch-grafen , som har 11 hörn, men den har en maximal grad på 5 och är inte regelbunden.

Grafen är inte vertextransitiv - automorfismgruppen har bara en vertexbana med längd 8 och en med längd 4.

Enligt Brooks teorem , har varje -regelbunden graf (förutom udda cykler och klickar) ett kromatiskt tal som inte överstiger . Dessutom, tack vare Erdős, har det varit känt sedan 1959 att för alla och det finns färgade grafer med omkrets . Baserat på dessa två resultat och några exempel, inklusive Chwatala-grafen, antog Branko Grünbaum 1970 att det för vilken som helst och det finns en -färgad -regelbunden graf med omkrets . Chvatala-grafen ger en lösning på denna gissning för fallet = = 4. Grünbaums gissning vederlagdes för tillräckligt stor av Johansen [1] , som visade att det kromatiska antalet grafer utan trianglar är , där är den maximala graden av hörn, och betyder "O" är stort . Trots denna vederläggning är det fortfarande ett intressant problem att hitta exempel på -färgade -regelbundna grafer med små värden och stor omkrets. $k$ $k$ $k$ $l$ $k$ $l$ $k$ $l$ $k$ $k$ $l$ $k$ $l$ $k$ $O(\Delta /\log \Delta )$ $\Delta$ $O$ $k$ $k$ $k$

Bruce Reids alternativa gissning [1] säger att triangelfria grafer med hög vertexgrad bör ha avsevärt lägre kromatiskt tal än grad, och mer generellt att grafer med maximal grad och maximal storlek klick bör ha kromatiskt nummer: $\Delta$ $\omega$

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

Fallet med denna gissning följer för tillräckligt stora sådana av Johansens resultat. Chvatala-grafen visar att avrundning uppåt i Reids gissningar är väsentlig, eftersom för Chvatala-grafen , som är mindre än det kromatiska talet, men blir lika med det när man avrundar uppåt. $\omega =2$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

Graph Graft är Hamiltonian och spelar en nyckelroll i Fleischner och Sabidoussis [2] bevis på att det är ett NP-komplett problem att kontrollera om en triangelfri Hamiltonian graf kan vara trefärgad .

Det karakteristiska polynomet i Chvatala-grafen är lika med . Tatta-polynomet i Chwatala-grafen beräknades 2008 [3] . $(x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)$

Grafens oberoende nummer är 4.

Galleri

Det kromatiska talet för greve Chvatal är 4.
Chwatal-grafens kromatiska index är 4.
Greve tog tag i Hamiltons .
Alternativ teckning av greve Khvatala.

Litteratur

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science. — Washington, DC, USA: IEEE Computer Society, 2008. — s. 677–686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 . .
V. Chvatal. Den minsta triangelfria 4-kromatiska 4-regelbundna grafen // Journal of Combinatorial Theory. - 1970. - T. 9 , nr. 1 . — S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Paul Erds. Grafteori och sannolikhet // Canadian Journal of Mathematics. - 1959. - T. 11 . — S. 34–38 . - doi : 10.4153/CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. 3-färgbarhet av 4-regelbundna Hamiltonian-grafer // Journal of Graph Theory. - 2002. - T. 42 , nr. 2 . — S. 125–140 . - doi : 10.1002/jgt.10079 . .
B. Grunbaum. Ett problem i graffärgning // American Mathematical Monthly. - Mathematical Association of America, 1970. - V. 77 , nr. 10 . — S. 1088–1092 . - doi : 10.2307/2316101 . — . .
vass. ω, Δ och χ // Journal of Graph Theory. - 1998. - T. 27 , nr. 4 . — S. 177–212 . - doi : 10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K . .

Länkar

Weisstein, Eric W. Chvátal Graph (engelska) på Wolfram MathWorld- webbplatsen .