본문 바로가기
  • Home

A Polynomial Time Algorithm for Edge Coloring Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2013, 18(11), pp.159-165
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2022 are currently being built.