Grafo de Chvátal
Aspeto
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