Vertex coloring of plane graphs

Abstract

사색 문제로 알려진 사색 이론은 지도 상의 서로 인접한 두 영역들이 같은 색상을 가지지 않도록 채색할 때, 네 가지 색상만으로도 조건을 충분히 만족시키며 모든 영역들을 채색할 수 있다는 이론이다. 사색 이론은 평면 그래프의 꼭짓점을 채색하는 문제로 해석될 수 있다. 평면 그래프의 꼭짓점을 채색하기 위해 우리는 다음과 같은 방법에 대해 알아보도록 한다.

1. 주어진 지도를 그래프로 표현하고, 이 그래프를 포함하며 꼭짓점의 수는 같고 가능한 많은 모서리를 가지는 평면 그래프를 하나 찾는다. 2. 이 평면 그래프에서 차수가 3 이하인 꼭짓점이 있다면 제거한다. 3. 이 그래프에서 서로 인접하지 않으며 각각 어떤 차륜형 부분 그래프들의 중심이 되는 꼭짓점들로 이루어진 중심점 집합을 찾는다. 4. 중심점 집합에 원소가 아닌 꼭짓점들을 세 가지 색상로만 채색한다. 5. 중심점 집합의 원소가 되는 꼭짓점들을 앞의 세가지 색상과는 다른 네 번째 색상으로 채색한다. 6. 이 결과를 처음에 주어진 지도에 적용한다.

위와 같은 방법을 이용하여, 무작위로 생성된 꼭짓점의 개수가 40인 그래프를 채색하는 컴퓨터 실험에서 약 98%의 채색 성공률을 얻을 수 있었다. 이 채색 방법을 개선하는 것에 대해 논하도록 한다.

The four color theorem states that only four colors are needed to color the regions of any simple planar map so that any two adjacent regions have different colors. This theorem can be interpreted as finding a vertex coloring of plane graphs. This thesis suggests a method to find a vertex coloring of plane graphs with four available colors that includes the following steps:

(i) Convert the given map to a graph and find a maximal plane graph that contains the graph. (ii) Remove vertices of degree 3 from the maximal plane graph if they exist. (iii) Find a hubset that is a set of independent hubs of wheels. (iv) Color the vertices that are not the elements of the hubset with three available colors. (v) Color the vertices contained in the hubset with the fourth color. (vi) Finally, apply the coloring result to the given map.

Using this process, we obtained a 98% success rate in computer experiments for random graphs of order 40. We will discuss how to improve the coloring process.