Scholarlink

<p>The 2-colorable perfect matching problem asks whether a graph can be colored with two colors so that each node has exactly one neighbor with the same color as itself. We prove that this problem is NP-complete, even when restricted to 2-connected 3-regular planar graphs. In 1978, Schaefer proved that this problem is NP-complete in general graphs, and claimed without proof that the same result holds when restricted to 3-regular planar graphs. Thus we fill in the missing proof of this claim, while simultaneously strengthening to 2-connected graphs (which implies existence of a perfect matching). We also prove NP-completeness of <i>k</i>-colorable perfect matching, for any fixed <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="224_2025_10221_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年4月26日

查看全文
  • Erik D. Demaine,
  • Kritkorn Karntikoon,
  • Nipun Pitimanaaree

摘要

The 2-colorable perfect matching problem asks whether a graph can be colored with two colors so that each node has exactly one neighbor with the same color as itself. We prove that this problem is NP-complete, even when restricted to 2-connected 3-regular planar graphs. In 1978, Schaefer proved that this problem is NP-complete in general graphs, and claimed without proof that the same result holds when restricted to 3-regular planar graphs. Thus we fill in the missing proof of this claim, while simultaneously strengthening to 2-connected graphs (which implies existence of a perfect matching). We also prove NP-completeness of k-colorable perfect matching, for any fixed \(k \ge 2\) k ≥ 2 .