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

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

-
Celina de Figueiredo, Rio de Janeiro
Fine Hall 224

Given a class A of graphs and a decision problem X 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 X 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 Vušković who proved a structure theorem which led to solving the vertex-colouring problem in polynomial time. 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 class and of separating problems.