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.


Galeria

Bibliografia

  • 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.2585Acessível livremente, 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 .

Ligações externas