Resumen El problema de coloreo de grafos es uno de los problemas clásicos de la teoría de grafos y ha sido estudiado desde el siglo XIX. Más allá de su interés teórico, que ha motivado a la teoría de grafos durante más de un siglo, tiene una significativa importancia práctica debido a las numerosas situaciones de la vida real en las cuales surgen problemas que pueden ser modelados como un problema de coloreo de grafos. Pertenece a la clase de problemas NP-Hard. En la bibliografía pueden encontrarse gran cantidad de trabajos proponiendo algoritmos para su resolución, en su gran mayoría heurísticas. Haremos en esta charla una breve descripción de los más importantes y presentamos un algoritmo tipo Branch-and-Cut desarrollado en base a un nuevo modelo de programación entera. Se presentan resultados que muestran que este algoritmo es capaz de competir exitosamente con los algoritmos exactos conocidos.