Grev Hvatala

Grev Hvatala

Opkaldt efter	Vaclav Chvatal
Toppe	12
ribben	24
Radius	2
Diameter	2
Omkreds	fire
Automorfismer	8 ( D4 )
Kromatisk tal	fire
Kromatisk indeks	fire
Ejendomme	euler hamiltonian regelmæssig uden trekanter
Mediefiler på Wikimedia Commons

Graf Chvatala er en urettet graf med 12 hjørner og 24 kanter opdaget af Vaclav Chvatala i 1970.

Egenskaber

Grafen indeholder ikke trekanter - dens omkreds (længden af den mindste cyklus) er lig med fire. Grafen er 4 - regulær - hvert toppunkt har præcis fire naboer. Grafens kromatiske tal er 4 - den kan farves med fire farver, men ikke med tre. Som Chwatal opdagede, er dette en minimal 4-farvet 4-regulær trekantfri graf. En mindre trekantfri 4-farve graf er Grötzsch grafen , som har 11 hjørner, men den har en maksimal grad på 5 og er ikke regulær.

Grafen er ikke toppunkttransitiv - automorfigruppen har kun én toppunktsbane af længde 8 og en med længde 4.

Ved Brooks' sætning har enhver -regulær graf (undtagen ulige cyklusser og kliker) et kromatisk tal, der ikke overstiger . Takket være Erdős har det også været kendt siden 1959, at der findes farvede grafer med omkreds . Baseret på disse to resultater og nogle eksempler, herunder Chwatala-grafen, formodede Branko Grünbaum i 1970, at der for enhver, og der eksisterer en -farvet -regulær graf med omkreds . Chvatala-grafen giver en løsning på denne formodning for tilfældet = = 4. Grünbaums formodning blev tilbagevist for tilstrækkelig stor af Johansen [1] , som viste, at det kromatiske antal grafer uden trekanter er , hvor er den maksimale grad af hjørner, og betyder "O" er stort . På trods af denne afvisning er det fortsat et interessant problem at finde eksempler på -farvede -regulære grafer med små værdier og stor omkreds. $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 alternative formodning [1] siger, at trekantfrie grafer med høj toppunktsgrad bør have væsentligt lavere kromatisk tal end grad, og mere generelt at grafer med maksimal grad og maksimal størrelse klike skal have kromatisk tal: $\Delta$ $\omega$

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

Tilfældet med denne formodning følger for tilstrækkeligt store af Johansens resultat. Chvatala-grafen viser, at afrunding opad i Reids formodning er essentiel, da for Chvatala-grafen , som er mindre end det kromatiske tal, men bliver lig med det, når man runder op. $\omega =2$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

Graph Graft er Hamiltonsk og spiller en nøglerolle i Fleischner og Sabidoussis [2] bevis på, at det er et NP-komplet problem at kontrollere, om en trekantfri Hamiltonsk graf kan være trefarvet .

Chvatala-grafens karakteristiske polynomium er lig med . Chwatala-grafens Tatta-polynomium blev beregnet i 2008 [3] . $(x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)$

Grafens uafhængighedsnummer er 4.

Galleri

Grev Chvatals kromatiske tal er 4.
Chwatal-grafens kromatiske indeks er 4.
Greve tog fat i Hamiltons .
Alternativ tegning af grev 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 mindste trekantfrie 4-kromatiske 4-regulære graf // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 1 . — S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Paul Erds. Grafteori og sandsynlighed // Canadian Journal of Mathematics. - 1959. - T. 11 . — S. 34–38 . - doi : 10.4153/CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. 3-farverbarhed af 4-regulære Hamiltonske grafer // Journal of Graph Theory. - 2002. - T. 42 , no. 2 . — S. 125–140 . - doi : 10.1002/jgt.10079 . .
B. Grunbaum. Et problem i graffarvning // American Mathematical Monthly. - Mathematical Association of America, 1970. - V. 77 , no. 10 . — S. 1088–1092 . - doi : 10.2307/2316101 . — . .
siv. ω, Δ og χ // 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 . .

Grev Hvatala

Egenskaber

Galleri

Noter

Litteratur

Links