| Monday, April 2nd, 2012 | 4pm-5pm | Burnside 1205 |
Departments of Mathematics and Computing Science, Simon Fraser University
Optimal decompositions of claw-free trigraphs
(or, how I learned to stop worrying and love the structure theorem)
(or, how I learned to stop worrying and love the structure theorem)
Chudnovsky and Seymour's structure theorem for quasi-line and claw-free graphs has led to a multitude of recent results that exploit two structural operations: compositions of strips and thickenings. The full structure theorem is detailed and fairly intimidating, but from an algorithmic decomposition standpoint there is actually nothing to worry about (when α ≤ 4).
In this talk I will discuss what an optimal decomposition is, why it is unique (under reasonable assumptions), how we can find it in O(m2) time, and what this allows us to do.
Joint work with Maria Chudnovsky.