publication . Article . Other literature type . 1983

np completeness of finding the chromatic index of regular graphs

Leven, Daniel; Galil, Zvi;
  • Published: 01 Mar 1983 Journal: Journal of Algorithms, volume 4, pages 35-44 (issn: 0196-6774, Copyright policy)
  • Publisher: Elsevier BV
Abstract We show that it is NP complete to determine whether it is possible to edge color a regular graph of degree k with k colors for any k ⩾ 3. As a by-product of this result, we obtain a new way to generate k-regular graphs which are k-edge colorable.
free text keywords: Regular graph, Discrete mathematics, Combinatorics, Edge coloring, Pathwidth, Graph coloring, Chordal graph, Strongly regular graph, 1-planar graph, Random regular graph, Mathematics
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue