<p>Here's one very relevant looking result:</p>

<p>Koreas, Diamantis P. (1997), "The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3", <a href="http://dx.doi.org/10.1016/S0096-3003(96)00021-5" rel="nofollow"><em>Appl. Math. Comput.</em> 83 (1): 13–17</a>.</p>

<p>The title is self-explanatory.</p>

CC BY-SA 3.0
2016-07-05T09:16:47.577Z
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.)
domotorp
CC BY-SA 3.0
2016-07-05T07:12:10.387Z
2016-07-05T07:12:10.387Z
David Eppstein
<p>There is a nice <a href="http://www.sciencedirect.com/science/article/pii/0166218X9190010T" rel="nofollow noreferrer">paper</a> 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?</p>

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

CC BY-SA 3.0
2016-08-07T16:31:44.793Z
graphclasses.org has a list by class of the [complexity of testing whether a graph is 3-colourable](http://graphclasses.org/classes/problem_3-Colourability.html) and another for [testing whether it is k-colourable](http://graphclasses.org/classes/problem_Colourability.html). It also has a large list of [classes for which the chromatic number is bounded](http://graphclasses.org/classes/par_19.html).
Peter Taylor
CC BY-SA 3.0
2016-08-07T18:29:32.653Z
@Peter: I couldn't find chromatic index in the datebase.
domotorp
<graph-theory><np-hardness><graph-colouring>
What is known about the hardness of the chromatic index for restricted graph classes?
domotorp
# What is known about the hardness of the chromatic index for restricted graph classes?

(Asked by: username_0 on 2016-07-04)

There is a nice [paper](http://www.sciencedirect.com/science/article/pii/0166218X9190010T) 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>.

**Tags:** graph-theory, np-hardness, graph-colouring

> **Comments:**
> **username_1**: graphclasses.org has a list by class of the [complexity of testing whether a graph is 3-colourable](http://graphclasses.org/classes/problem_3-Colourability.html) and another for [testing whether it is k-colourable](http://graphclasses.org/classes/problem_Colourability.html). It also has a large list of [classes for which the chromatic number is bounded](http://graphclasses.org/classes/par_19.html).  
> **username_0**: @Peter: I couldn't find chromatic index in the datebase.  

---

## 1 answers

### Answer by username_2 on 2016-07-05. Score: 2

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](http://dx.doi.org/10.1016/S0096-3003(96)00021-5).

The title is self-explanatory.

> **Comments:**
> **username_0**: 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.)  

---

