평면의 채색수 알고리즘

다국어 초록 (Multilingual Abstract)

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≤χ(G)≤7 to which Hadwiger-Nelson proposed χ(G)≤7 and Soifer χ(G)≤9 I firstly propose an algorithm that obtains the minimum necessary chromatic number and show that χ(G)=3 is attainable by determining the chromatic number for Hadwiger-Nelson's hexagonal graph. The proposed algorithm obtains a chromatic number of χ(G)=4 assuming a Hadwiger-Nelson's hexagonal graph of 12 adjoining vertices, and again χ(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 χ(G)=4 using simple assigned rule of polynomial time complexity to color for a vertex with minimum degree.

참고문헌 (Reference)

1 이상운, "정점 색칠 문제의 다항시간 알고리즘" 한국컴퓨터정보학회 16 (16): 85-94, 2011

2 이상운, "간선 색칠 문제의 다항시간 알고리즘" 한국컴퓨터정보학회 18 (18): 159-165, 2013

3 H. Hadwiger, "Überdeckung des Euklidischen Raumes Durch Kongruentre Mengen" 4 : 238-242, 1945

4 G. K. Kristiansen, "Unit Distance Graphs in a Hexagonal Geometry"

5 E. W. Weisstein, "Unit Distance Graph" Wolfram Research, Inc

6 M. Payne, "Unit Distance Colouring Problems" Monash University 2007

7 A. Sofier, "The Mathematical Coloring Book:Mathematics of Coloring and the Colorful Life of Its Creators" Springer 2009

8 D. Coulson, "On the Chromatic Number of Plane Tilings" 77 : 191-196, 2004

9 E. W. Weisstein, "Hadwiger-Nelson Problem" Wolfram Research, Inc.

10 Wikipedia, "Hadwiger-Nelson Problem" Wikimedia Foundation Inc.

11 L. Lovász, "Geometric Representations of Graphs" Institute of Mathematics, Eötvös Loránd University 2007

12 D. Eppstein, "Geometric Graph Coloring Problems" Geometry Junkyard

13 G. Exoo, "Epsilon Unit Distance Graphs" 33 (33): 117-124, 2005

14 D. A. Meyer, "Coloring, Quantum Mechanics, and Euclid" University of California 2003

15 I. Hoffman, "Another Six-coloring of the Plane" 150 (150): 427-429, 1996

16 이상운, "4-색 알고리즘" 한국컴퓨터정보학회 18 (18): 113-120, 2013

17 T. R. Jensen, "25 Pretty Graph Colouring Problems" 299 (299): 167-169, 2001