Partition a graph with small diameter into two induced matchings

DOI10.1007/S11766-004-0031-ZMaRDI QIDQ2501435zbMATH OpenOpenAlexFDO

Authors Jinjiang Yuan, Aifeng Yang

Publication date 11 September 2006

Published in Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11766-004-0031-z

zbMATH Keywords

induced matching

Mathematics Subject Classification ID

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

Recommendations

• Cover a graph with small diameter by induced matchings
• On the complexity of matching cut in graphs of fixed diameter
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Partition the vertices of a graph into induced matchings
• Complexity and kernels for bipartition into degree-bounded induced graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Graph theory with applications
• Induced matchings
• Partition the vertices of a graph into induced matchings
• The complexity of satisfiability problems

Cited in

(4)

• Degree-constrained 2-partitions of graphs
• Cover a graph with small diameter by induced matchings
• Composing dynamic programming tree-decomposition-based algorithms
• Partition the vertices of a graph into induced matchings

This page was built for publication: Partition a graph with small diameter into two induced matchings

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