A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P-4-sparse graphs

作者：Bonomo Flavia; Duran Guillermo; Napoli Amedeo; Valencia Pabon Mario^*

来源：Information Processing Letters, 2015, 115(6-8): 600-603.

DOI：10.1016/j.ipl.2015.02.007

• Cluster deletion
• Sum coloring
• P-4-sparse
• Graph algorithms

In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph G and potentially optimal solutions for the minimum sum coloring problem in (G) over bar (i.e. the complement graph of G). We apply this correspondence to polynomially solve the cluster deletion problem in a subclass of P-4-sparse graphs that strictly includes P-4-reducible graphs.

• 出版日期2015-8
• 单位INRIA