3-SAT → Three-subcoloring of unit disk graphs Complexity open

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

Solution submitted Research history & proof on GitHub ↗

Why this question matters

The question combines geometric restrictions with a coloring rule that permits monochromatic cliques, beyond ordinary proper coloring.

Proper coloring hardness for unit disk graphs does not establish subcoloring hardness, because monochromatic cliques are allowed in the latter.

The reduction to construct

A source instance is an explicitly encoded Boolean formula with at most three literals per clause. Its outputs are satisfying Boolean assignments, or NO-SOLUTION when the formula is unsatisfiable.

The target supplies rational planar centers; vertices are adjacent exactly when their squared distance is at most one. Find three colors such that every monochromatic induced graph is a disjoint union of cliques, or report NO-SOLUTION.

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.

Gadget geometry must exclude unintended adjacencies and every valid subcoloring must recover a source assignment.

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-16. This summarizes the archived literature search on the date above. Unpublished, unindexed and overlooked work remains outside coverage; no new novelty assessment was performed.