Decomposing subcubic graphs into claws, paths or triangles

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2021-12, Vol.98 (4), p.557-588
Main Authors: Bulteau, Laurent, Fertin, Guillaume, Labarre, Anthony, Rizzi, Romeo, Rusu, Irena
Format: Article
Language:English
Subjects:
Apexes
Bioinformatics
Computational Complexity
Computer Science
Data Structures and Algorithms
decomposition
edge partition
Graph theory
Graphs
NP‐completeness
Partitioning
Polynomials
subcubic graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22713