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 (314Kb)
|Publisher Web site:||https://doi.org/10.1007/978-3-030-00256-5_23|
|Publisher statement:||The final publication is available at Springer via https://doi.org/10.1007/978-3-030-00256-5_23.|
|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|