There is a nice paper from 1991 that contains three diagrams about different graphclass-families showing what is known about the hardness of determining the chromatic index for them. Are there any news since then on these?

I'm most interested in what is known about graphs with a bounded chromatic number. My curiosity has been raised by https://mathoverflow.net/questions/238448/hypergraph-edge-colouring.


Here's one very relevant looking result:

Koreas, Diamantis P. (1997), "The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3", Appl. Math. Comput. 83 (1): 13–17.

The title is self-explanatory.

  • 5
    $\begingroup$ If the title is self-explanatory, then it is quite a trivial result. I mean the 1981 paper by Holyer that showed the NP-completeness of the chromatic index gave in fact a triangle-free cubic graph. (In a cubic graph, one can easily replace each triangle by a vertex when studying whether the chromatic index is 3 or 4.) $\endgroup$
    – domotorp
    Jul 5 '16 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.