NP-COMPLETENESS OF EDGE-COLORING SOME RESTRICTED GRAPHS

The problem of determining the chromatic index of a regular graph of fixed degree r greater-than-or-equal-to 3 is known to be NP-complete. We show that several other restricted versions of the problem are NP-complete. We show that the chromatic index problem restricted to regular comparability graphs of degree r greater-than-or-equal-to 3, perfect graphs, regular line graphs of odd degree r greater-than-or-equal-to 3, and claw-free graphs remains NP-complete, and thus resolve four open problems in Johnson's "The NP-completeness Column: an Ongoing Guide". We 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 C(k)-free graphs is NP-complete.