@article{ART001877301},
author={Sang-Un, Lee},
title={The Chromatic Number Algorithm in a Planar Graph},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={5},
pages={19-25}
TY - JOUR
AU - Sang-Un, Lee
TI - The Chromatic Number Algorithm in a Planar Graph
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 5
PB - The Korean Society Of Computer And Information
SP - 19
EP - 25
SN - 1598-849X
AB - 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 ≤ x(G) ≤ 7 to which Hadwiger-Nelson proposed x(G) ≤ 7 and Soifer x(G) ≤ 9 . I firstly propose an algorithm that obtains the minimum necessary chromatic number and show that x(G) = 3 is attainable by determining the chromatic number for Hadwiger-Nelson’s hexagonal graph. The proposed algorithm obtains a chromatic number of x(G) = 4 assuming a Hadwiger-Nelson’s hexagonal graph of 12 adjoining vertices, and again x(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 x(G) = 4 using simple assigned rule of polynomial time complexity to color for a vertex with minimum degree.
KW - Plane;Unit Distance Graph;Chromatic number;Degree
DO -
UR -
ER -
Sang-Un, Lee. (2014). The Chromatic Number Algorithm in a Planar Graph. Journal of The Korea Society of Computer and Information, 19(5), 19-25.
Sang-Un, Lee. 2014, "The Chromatic Number Algorithm in a Planar Graph", Journal of The Korea Society of Computer and Information, vol.19, no.5 pp.19-25.
Sang-Un, Lee "The Chromatic Number Algorithm in a Planar Graph" Journal of The Korea Society of Computer and Information 19.5 pp.19-25 (2014) : 19.
Sang-Un, Lee. The Chromatic Number Algorithm in a Planar Graph. 2014; 19(5), 19-25.
Sang-Un, Lee. "The Chromatic Number Algorithm in a Planar Graph" Journal of The Korea Society of Computer and Information 19, no.5 (2014) : 19-25.
Sang-Un, Lee. The Chromatic Number Algorithm in a Planar Graph. Journal of The Korea Society of Computer and Information, 19(5), 19-25.
Sang-Un, Lee. The Chromatic Number Algorithm in a Planar Graph. Journal of The Korea Society of Computer and Information. 2014; 19(5) 19-25.
Sang-Un, Lee. The Chromatic Number Algorithm in a Planar Graph. 2014; 19(5), 19-25.
Sang-Un, Lee. "The Chromatic Number Algorithm in a Planar Graph" Journal of The Korea Society of Computer and Information 19, no.5 (2014) : 19-25.