Grafo de Chvátal
 | Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Setembro de 2021) |
| 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[editar | editar código-fonte]
-
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.
Bibliografia[editar | editar código-fonte]
- 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.
Ligações externas[editar | editar código-fonte]
- Weisstein, Eric W. «Chvátal Graph» (em inglês). MathWorld