2025/08/04 by Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe +1 · 1 voice
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Graph theory and applications
paper · doi:10.1016/j.dam.2025.07.022
openalex publication_date 2025/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22
In this paper, we characterize in several manners the class of contraction perfect graphs which are the perfect graphs that remain perfect after the contraction of any edge set. We define the utter graph u ( G ) which is the graph whose stable sets are in bijection with the co-2-plexes of G , and prove that u ( G ) is perfect if and only if G is contraction perfect. Moreover, we exhibit the strong link between co-2-plexes and induced matchings and discuss its consequences according to known results on these problems. This yields several classes of graphs for which the maximum weighted co-2-plex is solvable in polynomial time. Finally, we show how our results extend to a new class of graphs for which finding a maximum weighted induced matching can be done in polynomial time.