Hrabě Hvatala

hrabě Hvatala

Pojmenoval podle	Václav Chvátal
Vrcholy	12
žebra	24
Poloměr	2
Průměr	2
obvod	čtyři
Automorfismy	8 ( D4 )
Chromatické číslo	čtyři
Chromatický index	čtyři
Vlastnosti	euler hamiltonský pravidelný bez trojúhelníků
Mediální soubory na Wikimedia Commons

Graf Chvátala je neorientovaný graf s 12 vrcholy a 24 hranami objevený Václavem Chvátalou v roce 1970.

Vlastnosti

Graf neobsahuje trojúhelníky - jeho obvod (délka nejmenšího cyklu) je roven čtyřem. Graf je 4 – pravidelný — každý vrchol má přesně čtyři sousedy. Chromatické číslo grafu je 4 – lze jej vybarvit čtyřmi barvami, ale třemi ne. Jak Chwatal zjistil, jedná se o minimální 4barevný 4-běžný graf bez trojúhelníků. Menší čtyřbarevný graf bez trojúhelníků je Grötzschův graf , který má 11 vrcholů, ale má maximální stupeň 5 a není pravidelný.

Graf není vertex-tranzitivní - skupina automorfismu má pouze jednu orbitu vrcholu o délce 8 a jednu o délce 4.

Podle Brooksova teorému má každý -regulární graf (kromě lichých cyklů a klik) chromatické číslo nepřesahující . Také díky Erdősovi je od roku 1959 známo, že pro všechny existují barevné grafy s obvodem . Na základě těchto dvou výsledků a některých příkladů, včetně grafu Chwatala, Branko Grünbaum v roce 1970 usoudil, že pro všechny a existuje -barevný -pravidelný graf s obvodem . Chvatalův graf dává řešení této domněnky pro případ = = 4. Grünbaumovu domněnku vyvrátil pro dostatečně velkou Johansen [1] , který ukázal, že chromatický počet grafů bez trojúhelníků je , kde je maximální stupeň vrcholů a znamená , že "O" je velké . Navzdory tomuto vyvrácení zůstává zajímavým problémem najít příklady -barevných -pravidelných grafů s malými hodnotami a velkým obvodem. $k$ $k$ $k$ $l$ $k$ $l$ $k$ $l$ $k$ $k$ $l$ $k$ $l$ $k$ $O(\Delta /\log \Delta )$ $\Delta$ $Ó$ $k$ $k$ $k$

Alternativní domněnka Bruce Reida [1] uvádí, že grafy bez trojúhelníků s vysokým stupněm vrcholu by měly mít podstatně nižší chromatické číslo než stupeň a obecněji, že grafy s maximálním stupněm a maximální velikostí kliky by měly mít chromatické číslo: $\Delta$ $\omega$

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

Případ tohoto dohadu vyplývá pro dostatečně velké z Johansenova výsledku. Chvatala graf ukazuje, že zaokrouhlení nahoru v Reidově domněnce je zásadní, protože pro Chvatala graf , který je menší než chromatické číslo, ale při zaokrouhlování se mu rovná. $\omega =2$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

Grafový graf je hamiltonovský a hraje klíčovou roli v Fleischnerově a Sabidoussiho [2] důkazu , že kontrola, zda hamiltonovský graf bez trojúhelníků může být trojbarevný, je NP-úplný problém .

Charakteristický polynom Chvatala grafu je roven . Tattův polynom Chwatalova grafu byl vypočten v roce 2008 [3] . $(x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)$

Číslo nezávislosti grafu je 4.

Galerie

Chromatické číslo hraběte Chvátala je 4.
Chromatický index Chwatalova grafu je 4.
Hrabě popadl Hamiltony .
Alternativní kresba hraběte Khvataly.

Literatura

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: Sborník 49. výročního sympozia IEEE o základech informatiky v roce 2008. — Washington, DC, USA: IEEE Computer Society, 2008. — s. 677–686. — ISBN 978-0-7695-3436-7 . - doi : 10.1109/FOCS.2008.40 . .
V. Chvátal. Nejmenší 4-chromatický 4-pravidelný graf bez trojúhelníků // Journal of Combinatorial Theory. - 1970. - T. 9 , no. 1 . — S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Paul Erds. Teorie grafů a pravděpodobnost // Canadian Journal of Mathematics. - 1959. - T. 11 . — S. 34–38 . - doi : 10.4153/CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. 3-barvitelnost 4-regulárních hamiltonovských grafů // Journal of Graph Theory. - 2002. - T. 42 , no. 2 . — S. 125–140 . - doi : 10.1002/jgt.10079 . .
B. Grunbaum. Problém s vybarvováním grafů // American Mathematical Monthly. - Mathematical Association of America, 1970. - V. 77 , no. 10 . — S. 1088–1092 . - doi : 10.2307/2316101 . — . .
rákos. ω, Δ a χ // 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 . .

Odkazy

Weisstein, Eric W. Chvátal Graph (anglicky) na webu Wolfram MathWorld .