Conde Hvatala

Conde Hvatala

Lleva el nombre de	Václav Chvatal
picos	12
costillas	24
Radio	2
Diámetro	2
Circunferencia	cuatro
automorfismos	8 ( D4 )
Número cromático	cuatro
índice cromático	cuatro
Propiedades	euler hamiltoniano regular sin triangulos
Archivos multimedia en Wikimedia Commons

Graph Chvatala es un gráfico no dirigido con 12 vértices y 24 aristas descubierto por Vaclav Chvatala en 1970.

Propiedades

El gráfico no contiene triángulos : su circunferencia (la longitud del ciclo más pequeño) es igual a cuatro. El gráfico es 4 - regular : cada vértice tiene exactamente cuatro vecinos. El número cromático de la gráfica es 4 - se puede colorear con cuatro colores, pero no con tres. Como descubrió Chwatal, este es un gráfico libre de triángulos mínimos de 4 colores y 4 regulares. Un gráfico de 4 colores sin triángulos más pequeño es el gráfico de Grötzsch , que tiene 11 vértices, pero tiene un grado máximo de 5 y no es regular.

El gráfico no es transitivo de vértice : el grupo de automorfismos tiene solo una órbita de vértice de longitud 8 y una de longitud 4.

Por el teorema de Brooks , cualquier gráfico -regular (excepto ciclos impares y cliques) tiene un número cromático que no excede . Además, gracias a Erdős, se sabe desde 1959 que para cualquier y existen gráficos coloreados con circunferencia . Con base en estos dos resultados y algunos ejemplos, incluido el gráfico de Chwatala, Branko Grünbaum conjeturó en 1970 que para cualquier y existe un gráfico regular de color con circunferencia . El gráfico de Chvatala da una solución a esta conjetura para el caso = = 4. La conjetura de Grünbaum fue refutada por suficientemente grande por Johansen [1] , quien demostró que el número cromático de gráficos sin triángulos es , donde es el grado máximo de vértices, y significa que "O" es grande . A pesar de esta refutación, sigue siendo un problema interesante encontrar ejemplos de gráficos regulares -coloreados con valores pequeños y gran circunferencia. $k$ $k$ $k$ $yo$ $k$ $yo$ $k$ $yo$ $k$ $k$ $yo$ $k$ $yo$ $k$ $O(\Delta /\log \Delta )$ $\Delta$ $O$ $k$ $k$ $k$

La conjetura alternativa de Bruce Reid [1] establece que los gráficos sin triángulos con un alto grado de vértice deberían tener un número cromático sustancialmente más bajo que el grado y, de manera más general, que los gráficos con un grado máximo y una camarilla de tamaño máximo deberían tener un número cromático: $\Delta$ $\omega$

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

El caso de esta conjetura se sigue para las suficientemente grandes del resultado de Johansen. El gráfico de Chvatala muestra que el redondeo hacia arriba en la conjetura de Reid es esencial, ya que para el gráfico de Chvatala , que es menor que el número cromático, pero se vuelve igual a él cuando se redondea hacia arriba. ${\ estilo de visualización \ omega = 2}$ $\Delta$ $(\Delta +\omega +1)/2=7/2$

El Graph Graft es hamiltoniano y juega un papel clave en la prueba de Fleischner y Sabidoussi [2] de que verificar si un gráfico hamiltoniano sin triángulos puede ser tricolor es un problema NP-completo .

El polinomio característico del gráfico de Chvatala es igual a . El polinomio de Tatta del gráfico de Chwatala se calculó en 2008 [3] . ${\ estilo de visualización (x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)}$

El número de independencia del gráfico es 4.

Galería

El número cromático del Conde Chvatal es 4.
El índice cromático del gráfico Chwatal es 4.
El conde agarró a los Hamilton .
Dibujo alternativo del Conde Khvatala.

Literatura

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: Actas del 49º Simposio Anual IEEE de 2008 sobre Fundamentos de Ciencias de la Computación. — Washington, DC, EE. UU.: IEEE Computer Society, 2008. — págs. 677–686. — ISBN 978-0-7695-3436-7 . -doi : 10.1109/ FOCS.2008.40 . .
V. Chavatal. El gráfico 4-cromático 4-regular libre de triángulos más pequeño // Journal of Combinatorial Theory. - 1970. - T. 9 , núm. 1 . — S. 93–94 . - doi : 10.1016/S0021-9800(70)80057-6 . .
Pablo Erds. Teoría de grafos y probabilidad // Canadian Journal of Mathematics. - 1959. - T. 11 . — Pág. 34–38 . -doi : 10.4153 / CJM-1959-003-9 . .
Herbert Fleischner, Gert Sabidussi. Capacidad de 3 colores de gráficos hamiltonianos de 4 regulares // Journal of Graph Theory. - 2002. - T. 42 , núm. 2 . — S. 125–140 . -doi : 10.1002/ jgt.10079 . .
B. Grünbaum. Un problema en la coloración de gráficos // American Mathematical Monthly. - Asociación Matemática de América, 1970. - V. 77 , no. 10 _ — S. 1088–1092 . -doi : 10.2307/ 2316101 . — . .
Junco. ω, Δ y χ // Revista de teoría de grafos. - 1998. - T. 27 , núm. 4 . — S. 177–212 . - doi : 10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K . .

Enlaces

Weisstein, Eric W. Chvátal Graph (inglés) en el sitio web de Wolfram MathWorld .