2011/10/24 by Maria Chudnovsky, Andrew D. King, Chudnovsky, Maria +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1110.5111
19 pages, 2 figures. Revision: Fixed statement of Corollary 2 (only applies to quasi-line graphs) and updated references
openalex publication_date 2011/10/24 · arxiv created 2012/08/30 · arxiv updated 2012/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Chudnovsky and Seymour's structure theorem for claw-free graphs has led to a multitude of recent results that exploit two structural operations: \em compositions of strips and \em thickenings. In this paper we consider the latter, proving that every claw-free graph has a unique optimal \em antithickening, where our definition of \em optimal is chosen carefully to respect the structural foundation of the graph. Furthermore, we give an algorithm to 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.