What question did this study set out to answer?

The aim is to establish a polynomial-time algorithm to determine the 3-colorability of graphs.

May 12, 2026Open Access

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

Key Points

The aim is to establish a polynomial-time algorithm to determine the 3-colorability of graphs.
Introduced a subtractive label reduction algorithm named Procedure 3 for analyzing graph colorability.
Tracked the monotonic collapse of color degrees of freedom in graphs to identify non-3-colorable structures.
Utilized generalized Mycielskian graphs for testing the algorithm's scalability.
Proved the algorithm operates in O(n^3) time complexity.
Demonstrated that non-3-colorable graphs enter a deterministic parity loop.
Established that the 3-coloring problem is classified under P, indicating efficient solvability.

Abstract

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.

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

Key Points

Abstract

Cite This Study

Also Consider

Also Consider