Cutting Barnette graphs perfectly is hard
From MaRDI portal
Publication:6589850
Cites work
- scientific article; zbMATH DE number 4094812 (Why is no real title available?)
- scientific article; zbMATH DE number 3694608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1202982 (Why is no real title available?)
- scientific article; zbMATH DE number 2044946 (Why is no real title available?)
- scientific article; zbMATH DE number 3326387 (Why is no real title available?)
- A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
- A note on matching-cut in \(P_t\)-free graphs
- Algorithms solving the matching cut problem
- Applications of a Planar Separator Theorem
- Dimer problem in statistical mechanics-an exact result
- Disjoint dominating and 2-dominating sets in graphs
- Distance-two colourings of Barnette graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Finding induced trees
- Matching cut in graphs with large minimum degree
- Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
- Matching cutsets in graphs
- NP-completeness of some generalizations of the maximum matching problem
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
- On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
- On line graphs of subcubic triangle-free graphs
- On the complexity of \(k\)-SAT
- On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
- Parallel Processing and Applied Mathematics
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Recognizing decomposable graphs
- Reducibility among combinatorial problems
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- The Factorization of Linear Graphs
- The complexity of counting in sparse, regular, and planar graphs
- The complexity of the matching-cut problem for planar graphs and other graph classes
- The perfect matching cut problem revisited
- Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
- Which problems have strongly exponential complexity?
This page was built for publication: Cutting Barnette graphs perfectly is hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6589850)
