Decomposing subcubic graphs into claws, paths or triangles. Issue 4 (20th July 2021)

• Record Type: Journal Article
• Authors: Bulteau, Laurent; Fertin, Guillaume; Labarre, Anthony; Rizzi, Romeo; Rusu, Irena
• Is Part Of: Journal of graph theory. Volume 98:Issue 4(2021)
• Page Start: 557
• Page End: 588
• Publication Date: 2021-07-20
• Subjects: decomposition -- edge partition -- NP‐completeness -- subcubic graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22713
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Let S = { K 1, 3, K 3, P 4 } be the set of connected graphs of size 3. We study the problem of partitioning the edge set of a graph G into graphs taken from any nonempty S ′ ⊆ S . The problem is known to be NP ‐complete for any possible choice of S ′ in general graphs. In this paper, we assume that the input graph is subcubic (i.e., all its vertices have degree at most 3), and study the computational complexity of the problem of partitioning its edge set for any choice of S ′ . We identify all polynomial and NP ‐complete problems in that setting.