Grafo de Chvátal

Grafo de Chvátal
O grafo de Chvátal
Vértices	1
Arestas	24
Raio	2
Diâmetro	2
Cintura	4
Automorfismos	8 (D4
Número cromático	4
Índice cromático	4
Propriedades	Regular Hamiltoniano Livre de triângulos Euleriano

No campo matemático da teoria dos grafos, o grafo de Chvátal é um grafo não dirigido com 12 vértices e 24 arestas, descoberto por Václav Chvátal.

O grafo é livre de triângulos: a sua cintura (o comprimento de seu menor ciclo) é quatro. Ele é 4-regular: cada vértice tem exatamente quatro vizinhos. O seu número cromático é quatro: pode ser colorido usando quatro cores, mas não apenas três. Ele é, como Chvátal observou, o menor possível grafo 4-cromático 4-regular livre de triângulos; o único menor grafo 4-cromático livre de triângulos é o grafo de Grötzsch, que tem 11 vértices mas o seu grau máximo é 5 e não é regular.

• 
  O número cromático do grafo de Chvátal é 4.
• 
  O número cromático do grafo de Chvátal é 4.
• 
  O grafo de Chvátal é hamiltoniano.
• 
  Desenho alternativo do grafo de Chvátal.

• Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2008), «Computing the Tutte Polynomial in Vertex-Exponential Time», FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, ISBN 978-0-7695-3436-7, Washington, DC, USA: IEEE Computer Society, pp. 677–686, arXiv:0711.2585, doi:10.1109/FOCS.2008.40 .
• Chvátal, V. (1970), «The smallest triangle-free 4-chromatic 4-regular graph», Journal of Combinatorial Theory, 9 (1): 93–94, doi:10.1016/S0021-9800(70)80057-6 .
• Erdős, Paul (1959), «Graph theory and probability», Canadian Journal of Mathematics, 11: 34–38, doi:10.4153/CJM-1959-003-9 .
• Fleischner, Herbert; Sabidussi, Gert (2002), «3-colorability of 4-regular Hamiltonian graphs», Journal of Graph Theory, 42 (2): 125–140, doi:10.1002/jgt.10079 .
• Grünbaum, B. (1970), «A problem in graph coloring», Mathematical Association of America, American Mathematical Monthly, 77 (10): 1088–1092, JSTOR 2316101, doi:10.2307/2316101 .
• Reed, B. A. (1998), «ω, Δ, and χ», 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 .

• Weisstein, Eric W. «Chvátal Graph». MathWorld (em inglês)