publication . Other literature type . Article . 1981

The NP-Completeness of Edge-Coloring

Ian Holyer;
  • Published: 01 Nov 1981
  • Publisher: Society for Industrial & Applied Mathematics (SIAM)
Abstract
We show that it is NP-complete to determine the chromatic index of an arbitrary graph. The problem remains NP-complete even for cubic graphs.
Subjects
free text keywords: General Computer Science, General Mathematics, Discrete mathematics, Graph coloring, List coloring, Brooks' theorem, Fractional coloring, Edge coloring, Mathematics, Combinatorics, Foster graph, 1-planar graph, Complete coloring
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue