***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 6th October, 3:00 in Fine Hall 224.
 
Speaker: Celina de Figueiredo (Rio de Janeiro)

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

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.

                       -----------

Next week: Wesley Pegden

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)