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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.ipl.2013.05.014 | Inf. Process. Lett. |
Keywords | Field | DocType |
stable set problem,polynomial time,general max-coloring problem,cornaz-jost transformation,coloring problem,new graph class,graph coloring problem,computational complexity | Edge coloring,Discrete mathematics,Complete coloring,Combinatorics,Graph power,Fractional coloring,Cubic graph,List coloring,Mathematics,Voltage graph,Graph coloring | Journal |
Volume | Issue | ISSN |
113 | 18 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Flavia Bonomo | 1 | 226 | 28.95 |
Monia Giandomenico | 2 | 30 | 3.74 |
Fabrizio Rossi | 3 | 140 | 16.33 |