A Polynomial-Time Algorithm for the 3-Coloring Problem based on Local Odd Parity Structures

Key Points

• The aim is to present a new algorithm that effectively addresses the 3-coloring problem in polynomial time.
• Introduced a subtractive label reduction algorithm.
• Identified localized odd-parity structures.
• Applied a monotonic reduction process for efficiency.
• Demonstrated a polynomial-time solution for the 3-coloring problem.
• Provided a structural proof for determining graph colorability.
• Addressed significant implications for the P vs NP question.