Construction of k-matchings in graph products

DOI10.26493/2590-9770.1462.b03zbMath1502.05214arXiv2109.06755OpenAlexW4280526408MaRDI QIDQ5058206

Marc Hellmuth, Anna Lindeberg

Publication date: 19 December 2022

Published in: The Art of Discrete and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessmaximum matchingperfect matchinggraph product\(k\)-factor\(k\)-regular subgraphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) 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) Graph operations (line graphs, products, etc.) (05C76)

Uses Software

• TopoLayout

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A local prime factor decomposition algorithm
• Local algorithms for the prime factorization of strong product graphs
• Matrix representation of Husserl's part-whole-foundation theory
• Graph factors and factorization: 1985--2003: a survey
• The complexity of regular subgraph recognition
• Lexicographic product of extendable graphs
• An algorithm for computing simple \(k\)-factors
• A note on the complexity of finding regular subgraphs
• Matching theory
• One-factors and \(k\)-factors
• Matching preclusion number in product graphs
• Matching preclusion for \(n\)-grid graphs
• Factoring the Cartesian product of a cubic graph and a triangle
• Finding regular subgraphs in both arbitrary and planar graphs
• Existence of 3-regular subgraphs in Cartesian product of cycles
• Quasi-independence, homology and the unity of type: a topological theory of characters
• Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs
• Perfect matchings after vertex deletions
• On the 1-factors of n-connected graphs
• Enumeration of perfect matchings of a type of Cartesian products of graphs
• On the Complexity of General Graph Factor Problems
• PERFECT MATCHINGS AND GENUS OF SOME CARTESIAN PRODUCTS OF GRAPHS
• Fast recognition of partial star products and quasi cartesian products
• On Edge-Colorability of Cartesian Products of Graphs^*
• Graphs with 1-Factors
• 1-Factorizations of cartesian products of regular graphs
• An algorithmic proof of Tutte's f-factor theorem
• Paths, Trees, and Flowers
• An efficient method for decomposition of regular structures using graph products
• The Factorization of Linear Graphs
• The Factors of Graphs

This page was built for publication: Construction of k-matchings in graph products