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
- 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
- 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
- Weisstein, Eric W. «Chvátal Graph». MathWorld (em inglês)