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
Autor principal: Bonomo, Flavia
Publicado: 2013
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:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo
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
id paper:paper_00200190_v113_n18_p649_Bonomo
record_format dspace
spelling paper:paper_00200190_v113_n18_p649_Bonomo2025-07-30T17:22:50Z A note on the Cornaz-Jost transformation to solve the graph coloring problem Bonomo, Flavia Computational complexity Graph coloring problem Graph operators Max-coloring problem Polynomial-time algorithm Coloring problems Graph class Graph coloring problem Max-coloring Polynomial-time Polynomial-time algorithms Stable set problems Algorithms Computational complexity Polynomial approximation Graph theory 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. Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2013 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Computational complexity
Graph coloring problem
Graph operators
Max-coloring problem
Polynomial-time algorithm
Coloring problems
Graph class
Graph coloring problem
Max-coloring
Polynomial-time
Polynomial-time algorithms
Stable set problems
Algorithms
Computational complexity
Polynomial approximation
Graph theory
spellingShingle Computational complexity
Graph coloring problem
Graph operators
Max-coloring problem
Polynomial-time algorithm
Coloring problems
Graph class
Graph coloring problem
Max-coloring
Polynomial-time
Polynomial-time algorithms
Stable set problems
Algorithms
Computational complexity
Polynomial approximation
Graph theory
Bonomo, Flavia
A note on the Cornaz-Jost transformation to solve the graph coloring problem
topic_facet Computational complexity
Graph coloring problem
Graph operators
Max-coloring problem
Polynomial-time algorithm
Coloring problems
Graph class
Graph coloring problem
Max-coloring
Polynomial-time
Polynomial-time algorithms
Stable set problems
Algorithms
Computational complexity
Polynomial approximation
Graph theory
description 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.
author Bonomo, Flavia
author_facet Bonomo, Flavia
author_sort Bonomo, Flavia
title A note on the Cornaz-Jost transformation to solve the graph coloring problem
title_short A note on the Cornaz-Jost transformation to solve the graph coloring problem
title_full A note on the Cornaz-Jost transformation to solve the graph coloring problem
title_fullStr A note on the Cornaz-Jost transformation to solve the graph coloring problem
title_full_unstemmed A note on the Cornaz-Jost transformation to solve the graph coloring problem
title_sort note on the cornaz-jost transformation to solve the graph coloring problem
publishDate 2013
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v113_n18_p649_Bonomo
http://hdl.handle.net/20.500.12110/paper_00200190_v113_n18_p649_Bonomo
work_keys_str_mv AT bonomoflavia anoteonthecornazjosttransformationtosolvethegraphcoloringproblem
AT bonomoflavia noteonthecornazjosttransformationtosolvethegraphcoloringproblem
_version_ 1840325981257072640

Ejemplares similares