Contractibility techniques as a closure concept

✍ Scribed by Zdeněk Ryjáček; R. H. Schelp

• Book ID: 102342494
• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 121 KB
• Volume: 43
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10103

✦ Synopsis

Abstract

We introduce a closure concept in the class of line graphs and claw‐free graphs based on contractibility of certain subgraphs in the line graph preimage. The closure can be considered as a common generalization and strengthening of the reduction techniques of Catlin and Veldman and of the closure concept introduced by the first author. We show that the closure is uniquely determined and the closure operation preserves the circumference of the graph. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 37–48, 2003