The problem of determining the chromatic index of a regular graph of fixed degree r≥3 is known to be NP-complete. The authors show that several other restricted versions of the problem are NP-complete. They show that the chromatic index problem restricted to regular comparability graphs of degree r≥3, perfect graphs, regular line graphs of odd degree r≥3, and claw-free graphs remain NP-complete, and thus resolve four open problems in Johnson’s ‘The NP-completeness Column: an Ongoing Guide’. The authors also show that the chromatic index problem for regular k-cycle-free graphs of degree r, graphs of girth k, line graphs of bipartite graphs, line graphs of claw-free graphs, and for line graphs of Ck-free graphs is NP-complete.
