Degree-four Matching Cut → Claw-free degree-six 2-Cut Complexity open

Model and version: gpt-6-astra
Date: Not recorded

Solution submitted Research history & proof on GitHub ↗

Why this question matters

A result would determine the exact maximum-degree boundary for 2-Cut on claw-free graphs.

The cited claw-free classification separates degree-five tractability from degree-seven hardness and identifies degree six as the missing boundary.

The reduction to construct

The source is a connected simple graph of maximum degree at most four. Its outputs are nontrivial vertex bipartitions with at most one opposite neighbor per vertex, or NO-SOLUTION.

The source is a connected simple graph of maximum degree four and asks for a nontrivial cut of crossing degree at most one. The target is connected, claw-free, of maximum degree six, and permits at most two opposite neighbors per vertex.

Construct deterministic polynomial-time maps F and G: F sends every legal source instance to a legal target instance, and G(x,y) is a valid source output for every valid output y of F(x). Preserve the stated threshold, domain and promises. The requested complexity conclusion is NP-hardness for the stated target problem.

Low-degree ports must transmit choices without introducing claws or allowing cuts that split a gadget incorrectly.

What a complete answer must include

Give explicit construction and recovery algorithms, a general proof for every legal input and every valid target output, and polynomial runtime and encoding-size bounds. Specify finite output encodings and handle NO-SOLUTION outputs when applicable. Tests compare recovered source outputs with independent source solutions.

References

Literature checked 2026-09-14. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.