A note on the Cornaz-Jost transformation to solve the graph coloring problem

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. © 2013 Elsevi...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Bonomo, F., Giandomenico, M., Rossi, F.
Formato: JOUR
Materias:
Computational complexity
Graph coloring problem
Graph operators
Max-coloring problem
Polynomial-time algorithm
Coloring problems
Graph class
Max-coloring
Polynomial-time
Polynomial-time algorithms
Stable set problems
Algorithms
Polynomial approximation
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
Descripción
Sumario: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. © 2013 Elsevier B.V.

Ejemplares similares