|Monday, April 2nd, 2012||4pm-5pm||Burnside 1205|
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.