@inproceedings { ,
title = {Connected Vertex Cover for (sP1+P5)-free graphs},
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 .},
conference = {44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2018).},
doi = {10.1007/978-3-030-00256-5\_23},
isbn = {9783030002558},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {279-291},
publicationstatus = {Published},
url = {https://durham-repository.worktribe.com/output/1144185},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2018},
author = {Johnson, M. and Paesani, G. and Paulusma, D.}
editor = {Brandstädt, Andreas and Köhler, Ekkehard and Meer, Klaus}
}