HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

A note on contracting claw-free graphs

Abstract : A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph operations permitted. By allowing any combination of these four operations we capture the following problems: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, (induced) spanning subgraphs, dissolutions and contractions. We show that these problems stay NP-complete even when the host and target belong to the class of line graphs, which form a subclass of the class of claw-free graphs, i.e., graphs with no induced 4-vertex star. A natural question is to study the computational complexity of these problems if the target graph is assumed to be fixed. We show that these problems may become computationally easier when the host graphs are restricted to be claw-free. In particular we consider the problems that are to test whether a given host graph contains a fixed target graph as a contraction.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-00980769
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Friday, April 18, 2014 - 4:43:56 PM
Last modification on : Wednesday, November 10, 2021 - 5:38:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 3:38:21 PM

File

2128-8288-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jiří Fiala, Marcin Kamiński, Daniël Paulusma. A note on contracting claw-free graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2013, Vol. 15 no. 2 (2), pp.223--232. ⟨10.46298/dmtcs.605⟩. ⟨hal-00980769⟩

Share

Metrics

Record views

79

Files downloads

810