Talk by Dr. Puck Rombach (Dept of Mathematics & Statistics, University of Vermont)

4/25/2019  Wilson Hall 1-144  3:10-4:00pm

Abstract:

We study the computational complexity of computing role colorings (for example, coupon colorings), of graphs in hereditary classes: classes that are closed under taking induced subgraphs. Many graph problems are NP-hard in general, but may be in P for certain classes of graphs. Instead of classifying problems, we can therefore fix a problem and classify graphs into “hard" and “easy" classes. Our current focus is hereditary classes, where such classifications are not usually possible. Unlike the minor-closed case, hereditary classes are not well founded with respect to the containment relation; there need not be a minimal element in a set of hereditary classes. In order to overcome this difficulty, Alekseev introduced the notion of a boundary class for a given problem P. If a family of graphs is defined by finitely many minimal forbidden induced subgraphs, then X is “hard" if and only if it contains a boundary class.