Disconnected cuts in claw-free graphs
From MaRDI portal
Publication:2186821
DOI10.1016/j.jcss.2020.04.005zbMath1450.05073OpenAlexW3017711003MaRDI QIDQ2186821
Erik Jan van Leeuwen, Barnaby Martin, Daniël Paulusma
Publication date: 9 June 2020
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9524/
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)
Related Items (2)
The complexity of contracting bipartite graphs into small cycles ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Algorithms for partition of some class of graphs under compaction and vertex-compaction
- The complexity of surjective homomorphism problems-a survey
- Parameterized complexity of induced graph matching on claw-free graphs
- The external constraint 4 nonempty part sandwich problem
- Parameterizing cut sets in a graph by the number of their components
- \(2K_{2}\) vertex-set partition into nonempty parts
- Covering graphs with few complete bipartite subgraphs
- Paw-free graphs
- List homomorphisms to reflexive graphs
- Linear-time recognition of circular-arc graphs
- \(2K_2\)-partition of some classes of graphs
- The P versus NP-complete dichotomy of some challenging problems in graph theory
- An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
- The computational complexity of disconnected cut and \(2 K_2\)-partition
- On disconnected cuts and separators
- Graph partitions with prescribed patterns
- Domination When the Stars Are Out
- A Polynomial Algorithm for 3-Compatible Coloring and the Stubborn List Partition Problem (The Stubborn Problem Is Stubborn No More)
- Bounding χ in terms of ω and Δ for quasi-line graphs
- Contractibility and NP-completeness
- List Partitions
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Minimal disconnected cuts in planar graphs
- FindingH-partitions efficiently
- Computational Complexity of Compaction to Reflexive Cycles
- Minimum Weighted Clique Cover on Strip-Composed Perfect Graphs
- Surjective H-colouring: New hardness results
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
This page was built for publication: Disconnected cuts in claw-free graphs
