Applied Math Seminar: Dr. Puck Rombach (U. Vermont) on "Role coloring graphs in hereditary classes"
- Thursday, April 25, 2019 from 3:00pm to 4:00pm
- Wilson Hall, 1-144 - view map
Applied Math Seminar
Dr. Puck Rombach (Mathematics & Statistics, U. Vermont)
Title: Role coloring graphs in hereditary classes
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.