- Series
- Graph Theory Seminar
- Time
- Tuesday, October 25, 2011 - 12:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Andrew King – Simon Fraser University
- Organizer
- Robin Thomas
Chudnovsky and Seymour's structure theorem for quasi-line graphs has led to
a multitude of recent results that exploit two structural operations: compositions of strips and thickenings. In this paper we prove that
compositions of linear interval strips have a unique optimal strip
decomposition in the absence of a specific degeneracy, and that every
claw-free graph has a unique optimal antithickening, where our two
definitions of optimal are chosen carefully to respect the structural
foundation of the graph. Furthermore, we give algorithms to find the optimal
strip decomposition in O(nm) time and find the optimal antithickening in
O(m2) time. For the sake of both completeness and ease of proof, we
prove stronger results in the more general setting of trigraphs. This gives
a comprehensive "black box" for decomposing quasi-line graphs that is not
only useful for future work but also improves the complexity of some
previous algorithmic results.
Joint work with Maria Chudnovsky.