New Optimization Problems on Perfect Graphs

Are there any new optimization problems (other that coloring and finding the size of the max clique) that are easier to solve for a perfect graph that for a general graph? Can we use any of the existing (future) recognition algorithms in order to do that?

Contributed by Mohammad Hajiaghayi

Back to the main index for Perfect Graphs.