Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

1980/01/01 by David P. Dailey · 5 citations
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Graph Labeling and Dimension Problems

paper · doi:10.1016/0012-365x(80)90236-8

crossref issued 1980/01/01 · crossref published 1980/01/01 · crossref published-print 1980/01/01 · openalex publication_date 1980/01/01 · crossref created 2003/01/10 · crossref deposited 2019/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/10 · crossref indexed 2026/08/05

Citations

• The complexity of theorem-proving procedures

Cited by

• Graph Colouring: A Visual Tour
• FO and MSO Model Checking on Temporal Graphs
• Solving Hard Computational Problems Efficiently: Asymptotic Parametric Complexity 3-Coloring Algorithm
• Four color theorem [wikipedia]
• Graph coloring [wikipedia]