A boundary class for the k-path partition problem.
Journal article
Korpelainen, Nicholas 2018. A boundary class for the k-path partition problem. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2018.05.009
| Authors | Korpelainen, Nicholas |
|---|---|
| Abstract | We establish the first known boundary class for the k-path partition problem and deduce that for a graph class defined by finitely many minimal forbidden induced subgraphs, the k-path partition problem remains NP-hard unless one of the forbidden induced subgraphs is a subcubic tree (a tree of maximum degree at most 3) with at most one vertex of degree 3. |
| Keywords | Hereditary graph classes; Boundary properties |
| Year | 2018 |
| Journal | Electronic Notes in Discrete Mathematics |
| Publisher | Elsevier |
| ISSN | 15710653 |
| Digital Object Identifier (DOI) | https://doi.org/10.1016/j.endm.2018.05.009 |
| Web address (URL) | http://hdl.handle.net/10545/622756 |
| hdl:10545/622756 | |
| Publication dates | 14 Jun 2018 |
| Publication process dates | |
| Deposited | 15 Jun 2018, 14:35 |
| Rights | Archived with thanks to Electronic Notes in Discrete Mathematics |
| Contributors | University of Derby |
| File | File Access Level Open |
| File | |
| File | File Access Level Open |
| File | File Access Level Open |
Permalink -
https://repository.derby.ac.uk/item/93289/a-boundary-class-for-the-k-path-partition-problem
Download files
68
total views91
total downloads7
views this month2
downloads this month
Export as
Related outputs
A new graph construction of unbounded clique-width.
Korpelainen, Nicholas 2016. A new graph construction of unbounded clique-width. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2016.11.005Infinitely many minimal classes of graphs of unbounded clique-width.
Collins, Andrew, Foniok, Jan, Korpelainen, Nicholas, Lozin, Vadim and Zamaraev, Viktor 2017. Infinitely many minimal classes of graphs of unbounded clique-width. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2017.02.012Well-quasi-order for permutation graphs omitting a path and a clique
Korpelainen, Nicholas, Atminas, Aistis, Brignall, Robert, Vatter, Vincent and Lozin, Vadim 2015. Well-quasi-order for permutation graphs omitting a path and a clique. The Electronic Journal of Combinatorics.