Cheap and Secure Web Hosting Provider : See Now

What NP-complete problem to reduce to k-Edge-Colorability to prove its NP-hardness?

, , No Comments
Problem Detail: 

What known NP-complete problem would one reduce to $k$-Edge-Colorability to prove that the latter is NP-hard?

Asked By : Omid Ebrahimi
Answered By : Juho

This is a classic result of Holyer [1]. The reduction is from 3-SAT, and the constructed graph is cubic.


[1] Holyer, Ian. "The NP-completeness of edge-coloring." SIAM Journal on Computing 10.4 (1981): 718-720.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49097

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback