A note on the Cornaz–Jost transformation to solve the graph coloring problem
2013, Information Processing Letters 113 (18), 649-652, 2013Citas: 6
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones
Autor(es)
Flavia Bonomo and Monia Giandomenico and Fabrizio Rossi
Abstract
In this note, we use a reduction by Cornaz and Jost from the graph (max-)coloring problem to the maximum (weighted) stable set problem in order to characterize new graph classes where the graph coloring problem and the more general max-coloring problem can be solved in polynomial time.