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

•We use a reduction by Cornaz and Jost from graph coloring to maximum stable set.•We characterize a new graph class where graph coloring is polynomial-time solvable.•We characterize a new graph class where max-coloring is polynomial-time solvable.•We analyze the reduction as a graph operator.

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.