### Optimal decompositions of quasi-line trigraphs

- Series
- Graph Theory Seminar
- Time
- Tuesday, October 25, 2011 - 12:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Andrew King – Simon Fraser University

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.