<p>It is known that for any multigraph $G$ on at most 8 vertices, $\chi'(G)$ is the maximum of the maximum degree and the ceiling of the odd-sets bound, see <a href="http://dx.doi.org/10.1016/S0012-365X%2896%2900364-0" rel="nofollow">http://dx.doi.org/10.1016/S0012-365X(96)00364-0</a> (so what you find with sage is not very surprising).</p>

<p>This recent arXiv manuscript gives some more references for your problem (top of page 3)
<a href="http://arxiv.org/pdf/1406.0757v1.pdf" rel="nofollow">http://arxiv.org/pdf/1406.0757v1.pdf</a></p>

<p>Beside bipartite graphs, non-trivial classes with the property you're looking for include series-parallel graphs.</p>

CC BY-SA 3.0
2014-06-17T13:45:07.840Z
Thank you. Is it known for perfect graphs?
joro
CC BY-SA 3.0
2014-06-17T13:48:55.097Z
I tried larger graphs (24 vertices) in sage and it appears true too.
joro
CC BY-SA 3.0
2014-06-17T13:43:19.830Z
2014-06-17T13:43:19.830Z
Louis Esperet
<p>Let $\chi'_f(G)$ be the fractional chromatic index.</p>

<p>For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$?</p>

<p>Since $\chi'_f(G)$ is computable in polynomial time,
 solving this gives tractable graph classes.</p>

<p>Experiments with Sage suggest this is true for
perfect graphs on up to $8$ vertices, though
Sage's implementation is not inefficient.</p>

CC BY-SA 3.0
2014-06-17T11:39:04.703Z
Sage is a free software. If you find a part of it too slow, come and write some code ! :-P
Nathann Cohen
CC BY-SA 3.0
2014-06-17T13:45:48.673Z
MO question about perfect graphs: https://mathoverflow.net/questions/172032/conjecture-for-perfect-graphs-the-fractional-chromatic-index-rounded-up-equals
joro
<graph-theory><graph-colouring>
For which graph classes the fractional chromatic index rounded up equals the chromatic index?
joro
# For which graph classes the fractional chromatic index rounded up equals the chromatic index?

(Asked by: username_0 on 2014-06-17)

Let $\chi'\_f(G)$ be the fractional chromatic index.

For which graph classes $\lceil \chi'\_f(G) \rceil = \chi'(G)$?

Since $\chi'\_f(G)$ is computable in polynomial time,
solving this gives tractable graph classes.

Experiments with Sage suggest this is true for
perfect graphs on up to $8$ vertices, though
Sage's implementation is not inefficient.

**Tags:** graph-theory, graph-colouring
> **Comments:**
> **username_1**: Sage is a free software. If you find a part of it too slow, come and write some code ! :-P  
> **username_0**: MO question about perfect graphs: https://mathoverflow.net/questions/172032/conjecture-for-perfect-graphs-the-fractional-chromatic-index-rounded-up-equals  

---

## 1 answers

### Answer by username_2 on 2014-06-17. Score: 4 | Accepted answer

It is known that for any multigraph $G$ on at most 8 vertices, $\chi'(G)$ is the maximum of the maximum degree and the ceiling of the odd-sets bound, see [http://dx.doi.org/10.1016/S0012-365X(96)00364-0](http://dx.doi.org/10.1016/S0012-365X%2896%2900364-0) (so what you find with sage is not very surprising).

This recent arXiv manuscript gives some more references for your problem (top of page 3)
<http://arxiv.org/pdf/1406.0757v1.pdf>

Beside bipartite graphs, non-trivial classes with the property you're looking for include series-parallel graphs.

> **Comments:**
> **username_0**: Thank you. Is it known for perfect graphs?  
> **username_0**: I tried larger graphs (24 vertices) in sage and it appears true too.  

---

