Connected Vertex Cover for (sP1+P5)-free graphs

Johnson, M.; Paesani, G.; Paulusma, D.

Abstract

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-free graphs if H is not a linear forest. On the other hand, the problem is known to be polynomial-time solvable for sP2 -free graphs for any integer s≥1 . We prove that it is also polynomial-time solvable for (sP1+P5) -free graphs for every integer s≥ 0 .

Citation

Johnson, M., Paesani, G., & Paulusma, D. (2018, June). Connected Vertex Cover for (sP1+P5)-free graphs. Presented at 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018)., Cottbus, Germany

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018).
• Start Date: Jun 27, 2018
• End Date: Jun 29, 2018
• Acceptance Date: Jul 15, 2018
• Online Publication Date: Sep 2, 2018
• Publication Date: Sep 2, 2018
• Deposit Date: Jul 30, 2018
• Publicly Available Date: Jul 31, 2018
• Print ISSN: 0302-9743
• Pages: 279-291
• Series Title: Lecture notes in computer science
• Series Number: 11159
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings.
• ISBN: 9783030002558
• DOI: https://doi.org/10.1007/978-3-030-00256-5_23
• Public URL: https://durham-repository.worktribe.com/output/1144185