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).