AffiliationUniversity of Derby
MetadataShow full item record
AbstractWe 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.
CitationKorpelainen, N. (2018) 'A Boundary Class for the k-Path Partition Problem', Electronic Notes in Discrete Mathematics, 67:49 .
JournalElectronic Notes in Discrete Mathematics
The following license files are associated with this item: