For a weighted graph G = (V,E), the maximum weighted k-coloring problem is to color a set of vertices of maximum weight using k colors. In the present paper, we are interested in solving this problem in comparability graphs. For these graphs, as shown by Cameron, the problem can be translated into a dual transportation problem. Let (G) denote the chromatic number of comparability graph G. We prove that when k is equal to (G) - 1, the problem can be solved more efficiently by finding a maximum weighted stable set in a bipartite graph. Maximum matching algorithms can be used in the unweighted case.
Paru en septembre 1991 , 10 pages