Research Work

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.

This work introduces a generalization of co-k-plexes and characterize their polytopes in natural and extended variable space for trees.