Buenas, tengo una duda acerca de la técnica de la coloración para descartar que un grafo tenga ciclos hamiltonianos, mi duda es si la misma se puede aplicar únicamente para grafos que admiten una 2-coloración o para cualquier k-coloración.
Desde ya, muchas gracias.
Hola Florencia. El argumento de la 2-coloración no se puede extender de forma simple para k-coloración con k>2. La idea es que con una 2-coloración los vértices de un camino hamiltoniano van a ir alternando colores entonces es simple concluir que la cantidad de vértices de un color y de otro no puede diferir en más de uno (de hecho deben ser la misma cantidad si el grafo tiene una cantidad par de vértices).