Cutting Barnette graphs perfectly is hard

Cites Work

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

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)