"Contractions in perfect graphs"
, accepted in Discrete Applied Mathematics, 2024
with Pierre Fouilhoux, Roland Grappe and Mathieu Lacroix
This work introduces a new class of perfect graphs called contraction perfect graphs—graphs that remain perfect after edge contractions. We characterize this class in several ways and show that they naturally lead to a family of graphs for which the maximum weighted co-2-plex problem is solvable in polynomial time via the ellipsoid method.