A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
Krzysztof Giaro, Marek Kubale · Discussiones Mathematicae Graph Theory · 2019
In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree 4 can be solved in O(n 2 ) time. This extends Jansen's result [K. Jansen, The optimum cost chromatic partition problem, in: