Cutting Barnette graphs perfectly is hard

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Algorithms solving the matching cut problem
Finding induced trees
Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
NP-completeness of some generalizations of the maximum matching problem
Which problems have strongly exponential complexity?
A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
A note on matching-cut in \(P_t\)-free graphs
Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
Distance-two colourings of Barnette graphs
Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
Disjoint dominating and 2-dominating sets in graphs
On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
On line graphs of subcubic triangle-free graphs
The Complexity of Counting in Sparse, Regular, and Planar Graphs
Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
Recognizing decomposable graphs
The complexity of the matching-cut problem for planar graphs and other graph classes
Applications of a Planar Separator Theorem
Finding a Maximum Cut of a Planar Graph in Polynomial Time
Reducibility among Combinatorial Problems
Matching cutsets in graphs
NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
Dimer problem in statistical mechanics-an exact result
The Factorization of Linear Graphs
Parallel Processing and Applied Mathematics
The perfect matching cut problem revisited
Matching cut in graphs with large minimum degree
On the complexity of \(k\)-SAT

This page was built for publication: Cutting Barnette graphs perfectly is hard