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

BONOMO, FLAVIA; DURAN, GUILLERMO; NAPOLI, AMEDEO; VALENCIA-PABON, MARIO

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Año: 2015 vol. 115 p. 600 - 603

0020-0190

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¯ (i.e. the complement graph of G). We apply this correspondence to polynomially solve the cluster deletion problem in a subclass of P4-sparse graphs that strictly includes P4-reducible graphs.