Groupe d’études et de recherche en analyse des décisions

G-91-38

A New Polynomial Time Algorithm for the Maximum Weighted ( (G) - 1)-Coloring Problem in Comparability Graphs

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.

, 10 pages