Subtractive Label Reduction and Parity Convergence: A Polynomial-Time Approach to the 3-Coloring Problem

This paper presents a refined subtractive label reduction algorithm, designated as Procedure 3, which determines the 3-colorability of a graph in O(n3) time. By tracking the monotonic collapse of color degrees of freedom, I prove that any non-3-colorable graph inevitably enters a deterministic ”Parity Loop.” This paper establishes the completeness of the algorithm, provides a rigorous proof of its polynomial time complexity, and demonstrates its scalability using generalized Mycielskian graphs. This framework yields a deterministic structural proof suggesting that the 3-coloring problem belongs to P.