Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs

Efficient algorithms are known for finding a maximum weight stable set, a minimum weighted clique covering, and a maximum weight clique of a vertex-weighted triangulated graph. However, there is no comparably efficient algorithm in the literature for finding a minimum weighted vertex coloring of such a graph. This paper gives an O(|V|² ) procedure for the problem (Algorithm 1). It then extends the procedure to the problem of finding in an arbitrary graph $G = (V,E)$ a maximal induced subgraph $G(W)$ color-equivalent (as defined in § 3) to a maximal triangulated subgraph $G(T)$ (Algorithm 2). Finally, it uses this latter algorithm as the main ingredient of a branch-and-bound procedure for the maximum weight clique problem in an arbitrary graph. Computational experience is presented on arbitrary random graphs with up to 2,000 vertices.