A note on the Cornaz-Jost transformation to solve the graph coloring problem
- Bonomo, Flavia
- Giandomenico, Monia
- Rossi, Fabrizio
Publication date
June 2013
DOI Publisher
Elsevier BV Journal
Information Processing LettersAbstract
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.Fil: Bonomo, Flavia. Consejo Nacional de Invest.cientif.y Tecnicas. Oficina de Coordinacion Administrativa Ciudad Universitaria. Instituto de Investigaciones Matematicas;Fil: Giandomenico, Monia. Università di L’Aquila. Dipartimento di Informatica, Italia;Fil: Rossi, Fabrizio. Università di L’Aquila. Dipartimento di Informatica, Italia
Add to ORKG