@article{ART001821023},
author={Sang-Un, Lee},
title={A Polynomial Time Algorithm for Edge Coloring Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2013},
volume={18},
number={11},
pages={159-165}
TY - JOUR
AU - Sang-Un, Lee
TI - A Polynomial Time Algorithm for Edge Coloring Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2013
VL - 18
IS - 11
PB - The Korean Society Of Computer And Information
SP - 159
EP - 165
SN - 1598-849X
AB - This paper proposes a O(E) polynomial-time algorithm that has been devised to simultaneously solve edge-coloring problem and graph classification problem both of which remain NP-complete.
The proposed algorithm selects an edge connecting maximum and minimum degree vertices so as to determine the number of edge coloring χ′(G′). Determined χ′(G′) is in turn either △(G) or △(G)+1.
Eventually, the result could be classified as class 1 if χ′(G′)= △(G) and as category 2 if χ′(G′)= △(G)+1. This paper also proves Vizing's planar graph conjecture, which states that 'all simple, planar graphs with maximum degree six or seven are of class one, closing the remaining possible case', which has known to be NP-complete.
KW - Chromatic Index;Maximum Degree;Minimum Degree;Class;NP-complete
DO -
UR -
ER -
Sang-Un, Lee. (2013). A Polynomial Time Algorithm for Edge Coloring Problem. Journal of The Korea Society of Computer and Information, 18(11), 159-165.
Sang-Un, Lee. 2013, "A Polynomial Time Algorithm for Edge Coloring Problem", Journal of The Korea Society of Computer and Information, vol.18, no.11 pp.159-165.
Sang-Un, Lee "A Polynomial Time Algorithm for Edge Coloring Problem" Journal of The Korea Society of Computer and Information 18.11 pp.159-165 (2013) : 159.
Sang-Un, Lee. A Polynomial Time Algorithm for Edge Coloring Problem. 2013; 18(11), 159-165.
Sang-Un, Lee. "A Polynomial Time Algorithm for Edge Coloring Problem" Journal of The Korea Society of Computer and Information 18, no.11 (2013) : 159-165.
Sang-Un, Lee. A Polynomial Time Algorithm for Edge Coloring Problem. Journal of The Korea Society of Computer and Information, 18(11), 159-165.
Sang-Un, Lee. A Polynomial Time Algorithm for Edge Coloring Problem. Journal of The Korea Society of Computer and Information. 2013; 18(11) 159-165.
Sang-Un, Lee. A Polynomial Time Algorithm for Edge Coloring Problem. 2013; 18(11), 159-165.
Sang-Un, Lee. "A Polynomial Time Algorithm for Edge Coloring Problem" Journal of The Korea Society of Computer and Information 18, no.11 (2013) : 159-165.
