Bipartite List 3-Coloring → Seven connected coloring bundles Complexity open

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

Solution submitted Research history & proof on GitHub ↗

Why this question matters

This tests the effect of connectivity requirements on a small fixed collection of coloring bundles.

Connected-bundle coloring with an unrestricted bundle count is already hard. The proposed contribution is the fixed seven-bundle restriction, not the unrestricted problem.

The reduction to construct

The source gives a simple bipartite graph and, for every vertex, an explicit list contained in {1,2,3}. Its outputs are proper colorings respecting all lists, or NO-SOLUTION; empty lists are allowed.

The target gives a finite simple bipartite graph H with an ordered partition into seven nonempty connected vertex sets. The first six are singleton bundles of weights 4096, 1024, 256, 64, 16 and 4; the seventh has weight 1. A valid output is a proper coloring by positive integers for which the sum, over bundles, of weight times maximum color is at most 5823, or 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.

Weights and connectors must force every accepted bundle assignment to respect the source lists.

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.