Matching cutsets in graphs

DOI10.1002/JGT.3190130502zbMATH Open0725.05055OpenAlexW2046680668MaRDI QIDQ5203060FDOQ5203060

Authors: Augustine Moshi 

Publication date: 1989

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190130502

Recommendations

• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• scientific article; zbMATH DE number 2044946
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Matching cutsets in graphs of diameter 2
• Algorithms Solving the Matching Cut Problem

zbMATH Keywords

connected graphmatching cutsetLine graphsGraphs without a chordless circuit

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Cites Work

• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS

Cited In (38)

• Algorithms Solving the Matching Cut Problem
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• Extremal graphs having no matching cuts
• Secure sets and their expansion in cubic graphs
• Title not available (Why is that?)
• Vertex partitioning problems on graphs with bounded tree width
• Title not available (Why is that?)
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• 3-consecutive edge coloring of a graph
• Discontinuities in the complexities of some graph recognition problems
• Cutting Barnette graphs perfectly is hard
• Title not available (Why is that?)
• On stable cutsets in line graphs
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• The perfect matching cut problem revisited
• The perfect matching cut problem revisited
• \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
• Complexity results for two kinds of colored disconnections of graphs
• Algorithms solving the matching cut problem
• Satisfactory graph partition, variants, and generalizations
• The sandwich problem for decompositions and almost monotone properties
• Parameterized complexity of perfectly matched sets
• Matching cutsets in graphs of diameter 2
• Title not available (Why is that?)
• Decycling with a matching
• A characterization of extremal graphs with no matching-cut
• Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The complexity of the perfect matching-cut problem
• On stable cutsets in graphs
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Matching of \(5-\gamma \)-critical leafless graph with a cut edge
• On stable cutsets in claw-free graphs and planar graphs
• On structural parameterizations of the matching cut problem
• Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
• Matching cut in graphs with large minimum degree
• Finding matching cuts in \(H\)-free graphs

This page was built for publication: Matching cutsets in graphs

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