Applied Math Seminar: Dr. Puck Rombach (U. Vermont) on "Role coloring graphs in hereditary classes"
When:
 Thursday, April 25, 2019 from 3:00pm to 4:00pm
Where:
 Wilson Hall, 1144  view map
Description:

Applied Math Seminar
Dr. Puck Rombach (Mathematics & Statistics, U. Vermont)
Title: Role coloring graphs in hereditary classes
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 NPhard 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 minorclosed 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.
Contact:
Share: