Packing $k$-Matchings and $k$-Critical Graphs

DOI10.1137/16M1092921zbMath1379.05088MaRDI QIDQ4602858

David B. Hartvigsen

Publication date: 7 February 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

matchingpackingpolynomial algorithmcritical graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced graph packing problems
• Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
• Chain packing in graphs
• Graph factors and factorization: 1985--2003: a survey
• An extension of matching theory
• Packings by cliques and by finite families of graphs
• General factors of graphs
• Fractional matchings and the Edmonds-Gallai theorem
• Undirected distances and the postman-structure of graphs
• On matroids induced by packing subgraphs
• f-factors and related decompositions of graphs
• Packing subgraphs in a graph
• An extension of Tutte's 1-factor theorem
• Generalized partitions of graphs
• Efficient subgraphs packing
• Optimal packing of induced stars in a graph
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Restricted \(t\)-matchings in bipartite graphs
• The Edmonds-Gallai decomposition for the \(k\)-piece packing problem
• Packing paths of length at least two
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Polyhedron of triangle-free simple 2-matchings in subcubic graphs
• The superstar packing problem
• Matchings of cycles and paths in directed graphs
• Independent packings in structured graphs
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• On the Complexity of General Graph Factor Problems
• Linear Systems for Constrained Matching Problems
• On Restricted Two-Factors
• Perfect triangle-free 2-matchings
• Integer and Fractional Matchings
• Packing paths in digraphs
• Graphs with the balas—uhry property
• The Nonnegative Node Weight j-Restricted k-Matching Problems
• Matroids Induced by Packing Subgraphs
• Paths, Trees, and Flowers
• The k‐piece packing problem
• Maximum matching and a polyhedron with 0,1-vertices
• The factorization of graphs. II
• The Factorization of Linear Graphs
• The Factors of Graphs
• A Short Proof of the Factor Theorem for Finite Graphs

This page was built for publication: Packing $k$-Matchings and $k$-Critical Graphs