You are here

  1. Home
  2. Dynamical Systems seminar - Minimal hereditary classes of graphs of unbounded tree-width or clique-width

Dynamical Systems seminar - Minimal hereditary classes of graphs of unbounded tree-width or clique-width

Dates
Wednesday, November 23, 2022 - 14:00 to 15:00

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.