본 논문은 지금까지 NP-완전인 난제로 알려진 4-색 정리를 선형시간 복잡도로 수기식과 컴퓨터를 활용하여 증명하는 알고리즘을 제안하였다. 제안된 알고리즘은 그래프 정점 집합 를 최대 독립집합 와 최소 정점 피복 집합 으로 정확히 양분하는 기법을 적용하여 에 첫 번째 색을 배정하고, 집합의정점들로 축소된 연결 그래프 를 대상으로 와 로 양분하여에 두 번째 색을 지정하였다. 집합의 정점들로 축소된 연결 그래프 를 대상으로 와 로 양분하여에 세 번째 색을 지정하였다. 마지막으로 를 로 하여 4번째 색을 배정하였다. 2개의 실제 지도 그래프와 2개의 평면 그래프를 대상으로 제안된 알고리즘을 적용한 결과 모든 그래프에서 채색수 를 찾는데 성공하였다. 결국, 제안된 “4-색 알고리즘”은 평면 그래프의 4-색을 결정하는 일반적인 알고리즘으로 적용할 수 있을 것이다.
이 논문은 현재까지 NP-완전인 난제로 알려진 4-색 정리를 선형시간 복잡도로 수기식과 컴퓨터를 활용해 증명하는 알고리즘을 제안했다.