Gráfico de Chvátal

En el campo matemático de la teoría de grafos , el gráfico de Chvátal es un gráfico no dirigido con 12 vértices y 24 aristas, descubierto por Václav Chvátal en 1970. Es el gráfico más pequeño que no tiene triángulos , es 4-regular y 4-cromático .

Coloración, grado y circunferencia.

El gráfico de Chvátal no tiene triángulos : su circunferencia (la longitud de su ciclo más corto) es cuatro. Es 4- regular : cada vértice tiene exactamente cuatro vecinos. Su número cromático es 4: se puede colorear con cuatro colores, pero no con sólo tres. Es, como observa Chvátal, el gráfico sin triángulos regulares 4 cromáticos más pequeño posible; El único gráfico más pequeño sin triángulos de 4 cromáticos es el gráfico de Grötzsch , que tiene 11 vértices pero tiene un grado máximo de 5 y no es regular. ^[1]

Según el teorema de Brooks , todo gráfico regular (excepto los ciclos impares y las camarillas) tiene un número cromático como máximo . También se sabía desde Erdős (1959) que, para todos y existen -gráficos cromáticos con circunferencia . ^[2] En relación con estos dos resultados y varios ejemplos, incluido el gráfico de Chvátal, Branko Grünbaum conjeturó que para todos y existen gráficos cromáticos regulares con circunferencia . ^[3] El gráfico de Chvátal resuelve el caso de esta conjetura. ^[1] La conjetura de Grünbaum fue refutada suficientemente por Johannsen, quien demostró que el número cromático de un gráfico sin triángulos es el grado máximo del vértice y introduce la notación O grande . ^[4] Sin embargo, a pesar de esta refutación, sigue siendo interesante encontrar ejemplos como el gráfico de Chvátal de gráficos regulares cromáticos de alta circunferencia para valores pequeños de . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\geq 3}$ ${\displaystyle \ell \geq 3}$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle k=\ell =4}$ ${\displaystyle k}$ ${\displaystyle O(\Delta /\log \Delta )}$ ${\displaystyle \Delta }$ ${\displaystyle O}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Una conjetura alternativa de Bruce Reed afirma que los gráficos sin triángulos de alto grado deben tener un número cromático significativamente menor que su grado y, de manera más general, que un gráfico con un grado máximo y un tamaño de camarilla máximo debe tener un número cromático ^[4] ${\displaystyle \Delta }$ ${\displaystyle \omega }$

$${\displaystyle \chi (G)\leq \left\lceil {\frac {\Delta +\omega +1}{2}}\right\rceil .}$$

${\displaystyle \omega =2}$ ${\displaystyle \Delta }$ ${\displaystyle (\Delta +\omega +1)/2=7/2}$

Otras propiedades

Este gráfico no es transitivo por vértices : su grupo de automorfismo tiene una órbita en vértices de tamaño 8 y una de tamaño 4.

El gráfico de Chvátal es hamiltoniano y juega un papel clave en la prueba de Fleischner y Sabidussi (2002) de que es NP-completo para determinar si un gráfico hamiltoniano sin triángulos tiene 3 colores. ^[5]

El polinomio característico del gráfico de Chvátal es . El polinomio de Tutte del gráfico de Chvátal ha sido calculado por Björklund et al. (2008). ^[6] ${\displaystyle (x-4)(x-1)^{4}x^{2}(x+1)(x+3)^{2}(x^{2}+x-4)}$

El número de independencia de esta gráfica es 4.

Galería

• 
  El número cromático de la gráfica de Chvátal es 4.
• 
  El índice cromático del gráfico de Chvátal es 4.
• 
  La gráfica de Chvátal es hamiltoniana .
• 
  Dibujo alternativo del gráfico de Chvátal.

Referencias

1. Chvátal, V. (1970), "El gráfico 4-regular 4 cromático sin triángulos más pequeño", Journal of Combinatorial Theory , 9 (1): 93–94, doi : 10.1016/S0021-9800(70)80057 -6
2. Erdős, Paul (1959), "Teoría de grafos y probabilidad", Canadian Journal of Mathematics , 11 : 34–38, doi : 10.4153/CJM-1959-003-9
3. Grünbaum, B. (1970), "Un problema de coloración de gráficos", American Mathematical Monthly , Mathematical Association of America, 77 (10): 1088–1092, doi :10.2307/2316101, JSTOR  2316101
4. Reed, BA (1998), "ω, Δ y χ", Journal of Graph Theory , 27 (4): 177–212, doi :10.1002/(SICI)1097-0118(199804)27:4<177 ::AID-JGT1>3.0.CO;2-K
5. Fleischner, Herbert; Sabidussi, Gert (2002), "3 colorabilidad de gráficos hamiltonianos de 4 regulares", Journal of Graph Theory , 42 (2): 125–140, doi :10.1002/jgt.10079, S2CID  20900014
6. Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Calcule el polinomio de Tutte en tiempo exponencial de vértices", FOCS '08: Actas del 49º Simposio anual del IEEE de 2008 sobre los fundamentos de la informática , Washington, DC, EE. UU.: IEEE Computer Society, págs. 677 –686, arXiv : 0711.2585 , doi :10.1109/FOCS.2008.40, ISBN 978-0-7695-3436-7, S2CID  10790973

enlaces externos

• Weisstein, Eric W. , "Gráfico de Chvátal", MathWorld