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 I). 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 section 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.