En el campo matemático de la teoría de grafos , el grafo de Chvátal es un grafo no dirigido con 12 vértices y 24 aristas, descubierto por Václav Chvátal ( 1970 ).
Gráfico de Chvátal | |
---|---|
Lleva el nombre de | Václav Chvátal |
Vértices | 12 |
Bordes | 24 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 4 |
Automorfismos | 8 ( D 4 ) |
Número cromático | 4 |
Índice cromático | 4 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Euleriano regular sin triángulo hamiltoniano |
Tabla de gráficos y parámetros |
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. Y su número cromático es 4: se puede colorear usando cuatro colores, pero no usando solo tres. Es, como observa Chvátal, el gráfico libre de triángulos 4-cromáticos 4-regulares más pequeño posible; el único gráfico más pequeño sin triángulos cromáticos 4 es el gráfico de Grötzsch , que tiene 11 vértices pero tiene un grado máximo de 5 y no es regular.
Este gráfico no es transitivo a vértices : el grupo de automorfismos tiene una órbita en vértices de tamaño 8 y otra de tamaño 4.
Según el teorema de Brooks , cada k- grafo regular (excepto los ciclos impares y las camarillas) tiene un número cromático como máximo k . También se sabía desde Erdős (1959) que, para cada k y l existen k -gráficos cromáticos con circunferencia l . En relación con estos dos resultados y varios ejemplos, incluido el gráfico de Chvátal, Branko Grünbaum ( 1970 ) conjetura que para cada k y l existen k -cromáticos k- gráficos regulares con circunferencia l . La gráfica de Chvátal resuelve el caso k = l = 4 de esta conjetura. La conjetura de Grünbaum fue refutada por una k suficientemente grande por Johannsen (ver Reed 1998 ), quien mostró que el número cromático de un gráfico sin triángulos es O (Δ / log Δ) donde Δ es el grado máximo del vértice y la O introduce la notación O grande . Sin embargo, a pesar de esta refutación, sigue siendo interesante encontrar ejemplos como el gráfico de Chvátal de gráficos k- cromáticos k -regulares de circunferencia alta para valores pequeños de k .
Una conjetura alternativa de Bruce Reed ( 1998 ) establece 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
El caso ω = 2 de esta conjetura se sigue, para Δ suficientemente grande, del resultado de Johanssen. El gráfico de Chvátal muestra que el redondeo en la conjetura de Reed es necesario, porque para el gráfico de Chvátal, (Δ + ω + 1) / 2 = 7/2, un número que es menor que el número cromático pero que se vuelve igual al cromático número cuando se redondea.
El gráfico de Chvátal es hamiltoniano y desempeña un papel clave en una demostración de Fleischner y Sabidussi (2002) de que es NP-completo para determinar si un gráfico hamiltoniano sin triángulos tiene 3 coloraciones.
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) .
El número de independencia de este gráfico es 4.
Galería
El número cromático del gráfico de Chvátal es 4.
El índice cromático del gráfico Chvátal es 4.
El gráfico de Chvátal es hamiltoniano .
Dibujo alternativo del gráfico de Chvátal.
Referencias
- Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), "Computing the Tutte Polynomial in Vertex-Exponential Time", FOCS '08: Actas del 49º Simposio Anual de IEEE sobre Fundamentos de la Ciencia de la Computación de 2008 , Washington, DC, EE. –686, arXiv : 0711.2585 , doi : 10.1109 / FOCS.2008.40 , ISBN 978-0-7695-3436-7.
- Chvátal, V. (1970), "El grafo 4-cromático 4-regular sin triángulos más pequeño", Journal of Combinatorial Theory , 9 (1): 93–94, doi : 10.1016 / S0021-9800 (70) 80057-6.
- Erdős, Paul (1959), "Teoría de grafos y probabilidad", Canadian Journal of Mathematics , 11 : 34–38, doi : 10.4153 / CJM-1959-003-9.
- Fleischner, Herbert; Sabidussi, Gert (2002), "3 colorabilidad de 4 grafos hamiltonianos regulares", Journal of Graph Theory , 42 (2): 125-140, doi : 10.1002 / jgt.10079.
- Grünbaum, B. (1970), "A problem in graph coloring", American Mathematical Monthly , Mathematical Association of America, 77 (10): 1088–1092, doi : 10.2307 / 2316101 , JSTOR 2316101.
- 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.
enlaces externos
- Weisstein, Eric W. "Gráfico de Chvátal" . MathWorld .