Speaker: Dan Cocks (The Open University)
Abstract: Many decision problems defined on a graph are generally hard, but are easy (i.e. an algorithm exists) when restricted to graphs in certain classes. In particular, these include graphs from classes with bounded tree-width or clique-width.
We seek to characterize those graphs at the boundary where hard problems become easy, that is, to identify "minimal" hereditary graph classes that are obstructions to bounded tree-width or clique-width.
This presentation is based on joint work with Robert Brignall.