标题： 完美切割 Barnette 图是困难的 显示英文标题

标题： Cutting Barnette graphs perfectly is hard

摘要： 一个完美匹配割是一个同时也是割集的完美匹配，或者等价地，一个在每个环上包含偶数条边的完美匹配。 对应的算法问题，完美匹配割，已知在子三次二分图中是NP难的 [Le 和 Telle, TCS '22]，但在平面图和三次图中的复杂性仍然是开放的。 我们通过证明完美匹配割在3连通三次二分平面图或Barnette图中是NP难的，同时解决了这两个问题。 在我们的工作之前，在输入仅为无向图的问题中，只有距离-2四色问题在Barnette图中已知是NP难的。 值得注意的是，如果Barnette猜想被反驳，哈密顿回路问题才会加入这个私人俱乐部。 显示英文摘要

摘要： A perfect matching cut is a perfect matching that is also a cutset, or equivalently a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, Perfect Matching Cut, is known to be NP-complete in subcubic bipartite graphs [Le & Telle, TCS '22] but its complexity was open in planar graphs and in cubic graphs. We settle both questions at once by showing that Perfect Matching Cut is NP-complete in 3-connected cubic bipartite planar graphs or Barnette graphs. Prior to our work, among problems whose input is solely an undirected graph, only Distance-2 4-Coloring was known NP-complete in Barnette graphs. Notably, Hamiltonian Cycle would only join this private club if Barnette's conjecture were refuted.