본 논문은 평면상의 거리가 1인 인접 정점들에 대해 서로 다른 색을 칠할 경우 최대로 필요한 색인 채색수를 찾는 문제를 연구하였다. 지금까지 채색수 상한 값은 4 ≤ x(G) ≤ 7 로 알려져 있으며, Hadwiger-Nelson은 x(G) ≤ 7, Soifer는 x(G) ≤ 9를 제안하였다. 먼저, 최소로 필요로 하는 채색수를 구하는 알고리즘을 제안하고,Hadwiger-Nelson의 정육각형 그래프를 대상으로 채색수를 구한 결과 x(G) = 3이 될 수 있음을 보였다. Hadwiger-Nelson의 정육각형 그래프를 12개 인접 정점으로 가정할 경우 x(G) = 4 를 구하였다. 또한, Soifer의8개 인접 정점 정사각형 그래프에 대해 채색수를 구한 결과 x(G) = 4임을 보였다. 결국, 제안된 알고리즘은 최소차수 정점부터 색을 배정하는 단순한 다항시간 규칙을 적용하여 평면의 최대 채색수는 x(G) = 4임을 제안한다.
본 연구는 평면상의 거리가 1인 인접 정점들에 대하여 서로 다른 색을 칠할 경우 최대로 필요한 색인 채색수를 찾는 문제를 연구했다.