# For which graph classes the fractional chromatic index rounded up equals the chromatic index?

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.

• Sage is a free software. If you find a part of it too slow, come and write some code ! :-P – Nathann Cohen Jun 17 '14 at 11:39
• MO question about perfect graphs: mathoverflow.net/questions/172032/… – joro Jun 17 '14 at 13:45

## 1 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 (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.

• Thank you. Is it known for perfect graphs? – joro Jun 17 '14 at 13:45
• I tried larger graphs (24 vertices) in sage and it appears true too. – joro Jun 17 '14 at 13:48