Partitioning vertices of graphs into paths of the same length

DOI10.1016/J.DAM.2025.04.054MaRDI QIDQ6965781zbMATH OpenFDO

Authors Oleg Duginov, D. S. Malyshev, D. B. Mokeev

Publication date 30 June 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.04.054

zbMATH Keywords

computational complexitypath packingpath partitionspecial graph classes

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) 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

• \(H\)-factors in dense graphs
• A \(5k\)-vertex kernel for \(P_2\)-packing
• A new approach on locally checkable problems
• A parameterized perspective on packing paths of length two
• A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
• Chain packing in graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Combinatorial optimization. Theory and algorithms
• Decomposing cubic graphs into connected subgraphs of size three
• Factors and factorizations of graphs. Proof techniques in factor theory
• Factors and factorizations of graphs—a survey
• Generalized planar matching
• Graph Classes: A Survey
• Graph theory
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 3977046 (Why is no real title available?)
• scientific article; zbMATH DE number 15366 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 2192124 (Why is no real title available?)
• Induced star partition of graphs
• Local transformations of graphs preserving independence number
• Matching theory
• Maximum bounded \(H\)-matching is Max SNP-complete
• On maximum \(P_3\)-packing in claw-free subcubic graphs
• On the Complexity of General Graph Factor Problems
• On the complexity of partitioning graphs into connected subgraphs
• On the maximum independent set problem in subclasses of planar graphs
• Packing paths perfectly
• Partitioning a split graph into induced subgraphs that are isomorphic to a path of order 3
• Partitioning graphs into induced subgraphs
• Partitioning perfect graphs into stars
• Planar 3DM is NP-complete
• The complexity of perfect packings in dense graphs
• The path partition problem and related problems in bipartite graphs
• Triangle packing in (sparse) tournaments: approximation and kernelization

This page was built for publication: Partitioning vertices of graphs into paths of the same length

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