The complexity of decomposing a graph into a matching and a bounded linear forest

DOI10.1002/JGT.23208MaRDI QIDQ6988422zbMATH OpenFDO

Authors Agnijo Banerjee, Adva Mond, Jan Petr, Julien Portier

Publication date 4 May 2025

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/JGT.23208

zbMATH Keywords

computational complexitygraph decompositionslinear forestsNP-completeness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• 3K2-decomposition of a graph
• A note on the decomposition of graphs into isomorphic matchings
• A Short Proof of the Factor Theorem for Finite Graphs
• An improved bound for the linear arboricity conjecture
• Covering planar graphs with forests
• Covering planar graphs with forests, one having bounded maximum degree
• Decomposition of Finite Graphs Into Forests
• Decompositions into two linear forests of bounded lengths
• Extremal aspects of graph and hypergraph decomposition problems
• General factors of graphs
• scientific article; zbMATH DE number 3974987 (Why is no real title available?)
• scientific article; zbMATH DE number 3717365 (Why is no real title available?)
• scientific article; zbMATH DE number 1953187 (Why is no real title available?)
• Matching theory
• NP-completeness of some problems of partitioning and covering in graphs
• On linear k-arboricity
• On the complexity of the disjoint paths problem
• Partitioning edges of a planar graph into linear forests and a matching
• Subcubic planar graphs of girth 7 are class I
• The Complexity of Multiterminal Cuts
• The factorization of graphs. II
• The Factors of Graphs
• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5

This page was built for publication: The complexity of decomposing a graph into a matching and a bounded linear forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6988422)