Critical hereditary graph classes: a survey

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so‐called ‘critical’ graph classes, which play an important role in the complexity analysis for the family. Recent progress in studying such classes is presented in the article.