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.
Galeria
Bibliografia . . . . . .
Ligações externas
Categoria:Grafos individuais Categoria:Grafos regulares