Complexity-separating graph classes for vertex, edge and total colouring

摘要

Given a class A of graphs and a decision problem pi belonging to NP, we say that a full complexity dichotomy of A was obtained if one describes a partition of A into subclasses such that pi is classified as polynomial or NP-complete when restricted to each subclass. The concept of full complexity dichotomy is particularly interesting for the investigation of NP-complete problems: as we partition a class A into NP-complete subclasses and polynomial subclasses, it becomes clearer why the problem is NP-complete in A. The class C of graphs that do not contain a cycle with a unique chord was studied by Trotignon and Vuskovic who proved a structure theorem which led to solving the vertex-colouring problem in polynomial time. In the present survey, we apply the structure theorem to study the complexity of edge-colouring and total-colouring, and show that even for graph classes with strong structure and powerful decompositions, the edge-colouring problem may be difficult. We discuss several surprising complexity dichotomies found in subclasses of C, and the concepts of separating problem proposed by David S. Johnson and the dual concept of separating class. (c) 2019 Elsevier B.V. All rights reserved.