3-SAT → Proper star colouring on split graphs Complexity open
Unsolved
Why this question matters
The restriction asks how much complexity survives when the graph decomposes into a clique and an independent set.
Ordinary proper coloring of split graphs is not the same task as excluding bichromatic four-vertex paths under a color budget.
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 gives a split graph and color budget k. Find a proper coloring with at most k colors in which no four-vertex path is bichromatic, 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.
Clique colors and independent-set constraints must force source choices without admitting alternative color identifications.
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
- Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs ↗
- 2025 journal version ↗
- Star Coloring on Some Subclasses of Chordal Graphs ↗
- The star and biclique coloring and choosability problems ↗
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.