We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Connected vertex cover for (sP1+P5)-free graphs.

Johnson, M. and Paesani, G. and Paulusma, D. (2018) 'Connected vertex cover for (sP1+P5)-free graphs.', in Graph-theoretic concepts in computer science : 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings. Cham: Springer, pp. 279-291. Lecture notes in computer science. (11159).


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 .

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:15 July 2018
Date deposited:31 July 2018
Date of first online publication:02 September 2018
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar