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; DURÁN, GUILLERMO; NAPOLI, AMEDEO; VALENCIA-PABON, MARIO
INFORMATION PROCESSING LETTERS
ELSEVIER SCIENCE BV
Lugar: Amsterdam; Año: 2015 vol. 115 p. 600 - 603
In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph and potentially optimal solutions for the minimum sum coloring problem in its complement. 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.