Matching cutsets in graphs of diameter 2
From MaRDI portal
Publication:955037
DOI10.1016/J.TCS.2008.07.002zbMATH Open1153.68037OpenAlexW1997541985MaRDI QIDQ955037FDOQ955037
Authors: Mieczysław Borowiecki, Katarzyna Jesse-Józefczyk 
Publication date: 18 November 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.07.002
Recommendations
- Matching cutsets in graphs
- On the complexity of matching cut in graphs of fixed diameter
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- Matchings in graphs with a given number of cuts
- Matching cut in graphs with large minimum degree
- Matching cut in graphs with large minimum degree
- On tight cuts in matching covered graphs
- On cuts and matchings in planar graphs
- A note on tight cuts in matching-covered graphs
- Finding matching cuts in \(H\)-free graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Modular decomposition and transitive orientation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sufficient conditions for \(\lambda'\)-optimality in graphs of diameter 2
- On stable cutsets in graphs
- Matching cutsets in graphs
- On stable cutsets in line graphs
- Size in maximal triangle-free graphs and minimal graphs of diameter 2
- Efficient and practical algorithms for sequential modular decomposition
- Graphs of diameter two with no 4-circuits
- Recognizing decomposable graphs
- Coloring graphs with stable cutsets
- Stable set bonding in perfect graphs and parity graphs
- Maximal and minimal vertex-critical graphs of diameter two
Cited In (15)
- Algorithms Solving the Matching Cut Problem
- Vertex partitioning problems on graphs with bounded tree width
- Improper C-colorings of graphs
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- 3-consecutive edge coloring of a graph
- On the complexity of matching cut in graphs of fixed diameter
- Title not available (Why is that?)
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
- \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs
- Algorithms solving the matching cut problem
- Satisfactory graph partition, variants, and generalizations
- On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
- 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 of diameter 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955037)
