[논문]평면의 채색수 알고리즘

이상운

doi:10.9708/jksci.2014.19.5.019

초록
AI-Helper

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

Abstract ▼ AI-Helper

In this paper, I seek the chromatic number, the maximum number of colors necessary when adjoining vertices in the plane separated apart at the distance of 1 shall receive distinct colors. The upper limit of the chromatic number has been widely accepted as $4{\leq}{\chi}(G){\leq}7$ to whic...

In this paper, I seek the chromatic number, the maximum number of colors necessary when adjoining vertices in the plane separated apart at the distance of 1 shall receive distinct colors. The upper limit of the chromatic number has been widely accepted as $4{\leq}{\chi}(G){\leq}7$ to which Hadwiger-Nelson proposed ${\chi}(G){\leq}7$ and Soifer ${\chi}(G){\leq}9$ I firstly propose an algorithm that obtains the minimum necessary chromatic number and show that ${\chi}(G)=3$ is attainable by determining the chromatic number for Hadwiger-Nelson's hexagonal graph. The proposed algorithm obtains a chromatic number of ${\chi}(G)=4$ assuming a Hadwiger-Nelson's hexagonal graph of 12 adjoining vertices, and again ${\chi}(G)=4$ for Soifer's square graph of 8 adjoining vertices. assert. Based on the results as such that this algorithm suggests the maximum chromatic number of a planar graph is ${\chi}(G)=4$ using simple assigned rule of polynomial time complexity to color for a vertex with minimum degree.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문은 평면상의 거리가 1인 인접 정점들에 대해 서로 다른 색을 칠할 경우 최대로 필요한 색인 채색수를 찾는 문제를 연구하였다. 지금까지 채색수 상한 값은 4 ≤ x(G) ≤ 7로 알려져 있으며, Soifer는 x(G) ≤ 9를 제안하였다.

가설 설정

여기서 평면이라 함은 유클 리드 평면 (Euclidean plane, ℝ2)으로 무한대 (∞)임을 가정한다[4,5].

제안 방법

제안된 알고리즘은 최소 차수 (minimum degree, δ(G))를 갖는 정점 u를 i번째 색 xi로 배정하고, u와 u에 이웃하는 정점 NG (u)인 정점 v의 간선을 모두 제거하였을때 남은 정점들 중에서 δ(G)인 정점을 xi색으로 배정하면서 정점들이 없을 때까지 반복 수행한다.
지금까지 채색수 상한 값은 4 ≤ x(G) ≤ 7로 알려져 있으며, Soifer는 x(G) ≤ 9를 제안하였다.

이론/모형

본 장에서는 그림 6과 같이 거리 1 인접 정점을 12개로 가정한 정육각형 Hadwiger-Nelson[2,8,9] 그래프와 인접 정점이 8개인 정사각형 Soifer[9] 그래프를 대상으로 제안된 알고리즘을 적용하여 최소 채색수를 구하여 본다.

성능/효과

결론적으로, 본 논문은 최소 차수 정점부터 색을 배정하는 단순한 규칙을 적용한 결과 평면의 채색수는 2 ≤ x(G) ≤ 4인 결론을 얻었다.
또한, Soifer의 8개 인접 정점 정사각형 그래프에 대해 채색수를 구한 결과 x(G) ≤ 9가 아닌 x(G) = 4임을 보였다.
먼저, 최소로 필요로 하는 채색수를 구하는 알고리즘을 제안하고, Hadwiger-Nelson의 6개 인접 정점 정육각형 그래프를 대상으로 채색수를 구한 결과 x(G) = 7이 아닌 x(G) = 3이 될 수 있음을 보였다. Hadwiger-Nelson의 6개 인접 정점 정육각형 그래프를 12개 인접 정점으로 가정할 경우에 대해 채색수를 구한 결과 x(G) = 4를 구하였다.
(e)는 각 정점에 색을 배정하여 표현한 그래프이다. 제안된 알고리즘을 적용한 결과 인접 정점들이 모두 다른 색으로 칠할 경우 3-색으로 가능함을 알 수 있다. 따라서 x(G) = 3이다.

후속연구

결론적으로, 본 논문은 최소 차수 정점부터 색을 배정하는 단순한 규칙을 적용한 결과 평면의 채색수는 2 ≤ x(G) ≤ 4인 결론을 얻었다. 따라서, 제안된 알고리즘은 평면의 채색수를 얻을 수 있는 다항시간 알고리즘을 제안하였으며, 본 알고리즘을 적용하면 지도나 평면에 색을 칠하는 게임 분야에 적용이 가능할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	단위거리 그래프의 채색수 상한값은?	평면 (plane) 상에서 거리가 1인 정점들을 간선으로 연결 하여 인접한 정점 간에는 다른 색을 칠할 경우, 최소로 요구 되는 채색수 (chromatic number, x(G)) 상한값 (upper bound)은 몇 개인가? 이 문제의 해답은 알려져 있지 않으며, 4 ≤ x(G) ≤ 7로 추정하고 있다[1-10]. 모든 단위거리 그래프 (unit distance graph)의 채색수 상한값은 x(G) = 4이다[3]. 따라서 하한값 (lower bound)은 4가 된다.
	평면의 최대 채색수와 최소 채색수는?	또한, Soifer의 8개 인접 정점 정사각형 그래프에 대해 채색수를 구한 결과 x(G) ≤ 9가 아닌 x(G) = 4임을 보였다. 결국, 평면의 최대 채색수 (상한 값)은 4이며, 최소 채색수 (하한값)은 2이다.
	평면 상에서 거리가 1인 정점들을 간선으로 연결하여 인접한 정점 간에는 다른 색을 칠할 경우, 최소로 요구되는 채색수의 상한값은 얼마로 추정하는가?	평면 (plane) 상에서 거리가 1인 정점들을 간선으로 연결 하여 인접한 정점 간에는 다른 색을 칠할 경우, 최소로 요구 되는 채색수 (chromatic number, x(G)) 상한값 (upper bound)은 몇 개인가? 이 문제의 해답은 알려져 있지 않으며, 4 ≤ x(G) ≤ 7로 추정하고 있다[1-10]. 모든 단위거리 그래프 (unit distance graph)의 채색수 상한값은 x(G) = 4이다[3].

참고문헌 (17)

T. R. Jensen and B. Toft, "25 Pretty Graph Colouring Problems," Discrete Mathematics, Vol. 299, No. 1-3, pp. 167-169, Feb. 2001.
Wikipedia, "Hadwiger-Nelson Problem," http://en.wikipedia.org/wiki/Hadwiger-Nelson_problem, Wikimedia Foundation Inc., 2014.
E. W. Weisstein, "Hadwiger-Nelson Problem" http://mathworld.wolfram.com/Hadwiger-NelsonProblem.html, MathWorld, Wolfram Research, Inc., 2014.
G. Exoo, "Epsilon Unit Distance Graphs," Discrete and Computational Geometry, Vol. 33, No. 1, pp. 117-124, Jan. 2005.

상세보기
M. Payne, "Unit Distance Colouring Problems," Bachelors Thesis, Monash University, 2007.
D. Eppstein, "Geometric Graph Coloring Problems," Geometry Junkyard, http://www.ics.uci.edu/-eppstein/junkyard/geom-color.html, Jul. 2009.
D. A. Meyer, "Coloring, Quantum Mechanics, and Euclid," Dept. of Mathematics, University of California/San Diago, Dec. 2003.
H. Hadwiger, "Uberdeckung des Euklidischen Raumes Durch Kongruentre Mengen," Portugal Mathematics, Vol. 4, pp. 238-242, 1945.
A. Sofier, "The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators," Springer, 2009.
L. Lovasz, "Geometric Representations of Graphs," Institute of Mathematics, Eotvos Lorand University, Budapest, 2007.
E. W. Weisstein, "Unit Distance Graph," http://mathworld.wolfram.com/UnitDistanceGraph.html, MathWorld, Wolfram Research, Inc., 2014.
G. K. Kristiansen, "Unit Distance Graphs in a Hexagonal Geometry," http://home20.inet.tele.dk/krisma/unit_distance_graphs.htm, Mar. 2005.
D. Coulson, "On the Chromatic Number of Plane Tilings," Journal of the Australian Mathematical Society, Vol. 77, pp. 191-196, Oct. 2004.

상세보기
I. Hoffman and A. Soifer, "Another Six-coloring of the Plane," Discrete Mathematics, Vol. 150, No. 1-3, pp. 427-429, Apr. 1996.

상세보기
S. U. Lee and M. B. Choi, "A Polynomial Time Algorithm for Vertex Coloring Problem," Journal of Korea Society of Computer Information, Vol. 16, No. 7, pp. 85-93, Jul. 2011.

원문보기 상세보기
S. U. Lee, "A Polynomial Time Algorithm for Edge Coloring Problem," Journal of Korea Society of Computer Information, Vol. 11, No. 11, pp. 159-165, Nov. 2013.

원문보기 상세보기
S. U. Lee, "The Four Color Algorithm," Journal of Korea Society of Computer Information, Vol. 18, No. 5, pp. 113-120, May. 2013.

원문보기 상세보기

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

평면의 채색수 알고리즘
The Chromatic Number Algorithm in a Planar Graph 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (17)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

평면의 채색수 알고리즘 The Chromatic Number Algorithm in a Planar Graph 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (17)

이 논문을 인용한 문헌

저자의 다른 논문 :

이상운 (191)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

평면의 채색수 알고리즘
The Chromatic Number Algorithm in a Planar Graph 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper