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.
A note on the Cornaz-Jost transformation to solve the graph coloring problem
ROSSI, FABRIZIO
2013-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
