Partition a graph with small diameter into two induced matchings

DOI10.1007/S11766-004-0031-ZzbMATH Open1099.05508OpenAlexW2000815825MaRDI QIDQ2501435FDOQ2501435

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

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

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)

Cites Work

• Title not available (Why is that?)
• Graph theory with applications
• The complexity of satisfiability problems
• Induced matchings
• Partition the vertices of a graph into induced matchings

Cited In (4)

• Partition the vertices of a graph into induced matchings
• Composing dynamic programming tree-decomposition-based algorithms
• Degree-constrained 2-partitions of graphs
• Cover a graph with small diameter by 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)