A NEW POLYNOMIAL-TIME ALGORITHM FOR THE MAXIMUM WEIGHTED (CHI(G) - 1)-COLORING PROBLEM IN COMPARABILITY-GRAPHS

For a weighted graph G = (V, E), the maximum weighted k-coloring probl em is to color a set of vertices of maximum weight using k colors. In this paper we are interested in solving this problem in comparability graphs. For these graphs, as shown by Cameron, the problem can be tran slated into a dual transportation problem. Let chi(G) denote the chrom atic number of a comparability graph G. We prove that when k is equal to chi(G)-1, the problem can be solved more efficiently by finding a m aximum weighted stable set in a bipartite graph. Maximum matching algo rithms can be used in the unweighted case.