Contele Hvatala

contele Hvatala

Numit după	Vaclav Chvatal
Vârfurile	12
coaste	24
Rază	2
Diametru	2
Circumferinţă	patru
Automorfisme	8 ( D4 )
Număr cromatic	patru
Indicele cromatic	patru
Proprietăți	euler hamiltonian regulat fără triunghiuri
Fișiere media la Wikimedia Commons

Graficul Chvatala este un grafic nedirecționat cu 12 vârfuri și 24 de muchii descoperit de Vaclav Chvatala în 1970.

Proprietăți

Graficul nu conține triunghiuri - circumferința sa (lungimea celui mai mic ciclu) este egală cu patru. Graficul este 4 - regulat - fiecare vârf are exact patru vecini. Numărul cromatic al graficului este 4 - poate fi colorat cu patru culori, dar nu cu trei. După cum a descoperit Chwatal, acesta este un grafic minim cu 4 culori și 4 triunghiuri regulate. Un grafic mai mic cu 4 culori fără triunghi este graficul Grötzsch , care are 11 vârfuri, dar are un grad maxim de 5 și nu este regulat.

Graficul nu este tranzitiv la vârf - grupul de automorfism are doar o orbită de vârf de lungime 8 și una de lungime 4.

După teorema lui Brooks , orice graf regulat (cu excepția ciclurilor impare și a clicurilor) are un număr cromatic care nu depășește . De asemenea, datorită lui Erdős, se știe din 1959 că pentru orice și există grafice colorate cu circumferință . Pe baza acestor două rezultate și a unor exemple, inclusiv a graficului Chwatala, Branko Grünbaum a presupus în 1970 că pentru orice și există un grafic regulat -colorat - cu circumferință . Graficul Chvatala oferă o soluție acestei presupuneri pentru cazul = = 4. Conjectura lui Grünbaum a fost respinsă pentru suficient de mare de Johansen [1] , care a arătat că numărul cromatic al graficelor fără triunghiuri este , unde este gradul maxim de vârfuri, și înseamnă „O” este mare . În ciuda acestei respingeri, rămâne o problemă interesantă să găsești exemple de grafice -colorate -regulate cu valori mici și circumferință mare. $k$ $k$ $k$ $l$ $k$ $l$ $k$ $l$ $k$ $k$ $l$ $k$ $l$ $k$ $O(\Delta /\log \Delta )$ $\Delta$ $O$ $k$ $k$ $k$

Conjectura alternativă a lui Bruce Reid [1] afirmă că graficele fără triunghi cu un grad ridicat de vârf ar trebui să aibă un număr cromatic substanțial mai mic decât gradul și, mai general, că graficele cu gradul maxim și dimensiunea maximă ar trebui să aibă un număr cromatic: $\Delta$ $\omega$

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

Cazul acestei conjecturi rezultă pentru cele suficient de mari din rezultatul lui Johansen. Graficul Chvatala arată că rotunjirea în sus în conjectura lui Reid este esențială, deoarece pentru graficul Chvatala , care este mai mic decât numărul cromatic, dar devine egal cu acesta la rotunjire în sus. $\omega =2$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

Grefa de graf este hamiltoniană și joacă un rol cheie în demonstrația lui Fleischner și Sabidoussi [2] că verificarea dacă un graf hamiltonian fără triunghi poate fi tricolor este o problemă NP-completă .

Polinomul caracteristic al graficului Chvatala este egal cu . Polinomul Tatta al graficului Chwatala a fost calculat în 2008 [3] . $(x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)$

Numărul de independență al graficului este 4.

Galerie

Numărul cromatic al contelui Chvatal este 4.
Indicele cromatic al graficului Chwatal este 4.
Contele a luat Hamiltoni .
Desen alternativ al contelui Khvatala.

Literatură

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: Proceedings of the 2008th Annual IEEE Symposium on Foundations of Computer Science. — Washington, DC, SUA: IEEE Computer Society, 2008. — pp. 677–686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 . .
V. Chvatal. Cel mai mic grafic 4-cromatic 4-regular fără triunghi // Journal of Combinatorial Theory. - 1970. - T. 9 , nr. 1 . — S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Paul Erds. Teoria graficelor și probabilitatea // Canadian Journal of Mathematics. - 1959. - T. 11 . — S. 34–38 . - doi : 10.4153/CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. 3-colorabilitatea graficelor hamiltoniene cu 4 regulate // Journal of Graph Theory. - 2002. - T. 42 , nr. 2 . — S. 125–140 . - doi : 10.1002/jgt.10079 . .
B. Grunbaum. O problemă în colorarea graficelor // American Mathematical Monthly. - Mathematical Association of America, 1970. - V. 77 , nr. 10 . — S. 1088–1092 . - doi : 10.2307/2316101 . — . .
stuf. ω, Δ și χ // 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 . .

Link -uri

Weisstein, Eric W. Chvátal Graph (engleză) pe site-ul web Wolfram MathWorld .