Decomposing Cubic Graphs into Connected Subgraphs of Size Three

DOI10.1007/978-3-319-42634-1_32zbMath1476.68194arXiv1604.08603OpenAlexW2963690687MaRDI QIDQ2817881

Irena Rusu, Romeo Rizzi, Guillaume Fertin, Laurent Bulteau, Anthony Labarre

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.08603

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Decomposing subcubic graphs into claws, paths or triangles ⋮ Pack graphs with subgraphs of size three

Cites Work

• Combinatorial and computational aspects of graph packing and graph decomposition
• Transversal structures on triangulations: A combinatorial study and straight-line drawings
• On the complexity of partitioning graphs into connected subgraphs
• Edge-Partitioning Regular Graphs for Ring Traffic Grooming with a Priori Placement of the ADMs
• Trois Types De Décompositions D'un Graphe En Chaînes
• The NP-Completeness of Some Edge-Partition Problems
• Graph Classes: A Survey
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Hard tiling problems with simple tiles

This page was built for publication: Decomposing Cubic Graphs into Connected Subgraphs of Size Three