Jiří Fiala ; Marcin Kamiński ; Daniël Paulusma - A note on contracting claw-free graphs

dmtcs:605 - Discrete Mathematics & Theoretical Computer Science, August 24, 2013, Vol. 15 no. 2 - https://doi.org/10.46298/dmtcs.605
A note on contracting claw-free graphsArticle

Authors: Jiří Fiala 1; Marcin Kamiński 2; Daniël Paulusma ORCID3

  • 1 Department of Applied Mathematics [Prague]
  • 2 Faculty of Mathematics, Informatics, and Mechanics [Warsaw]
  • 3 Department of Computer Science

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.


Volume: Vol. 15 no. 2
Section: Discrete Algorithms
Published on: August 24, 2013
Accepted on: June 9, 2015
Submitted on: April 5, 2012
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Algorithmic Aspects of Graph Coloring; Funder: UK Research and Innovation; Code: EP/G043434/1

3 Documents citing this article

Consultation statistics

This page has been seen 327 times.
This article's PDF has been downloaded 532 times.