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


Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:


**Conjecture** For perfect graphs $\lceil \chi'\_f(G) \rceil = \chi'(G)$


**Conjecture 2 (new)** For cubic claw-free perfect graphs $\lceil \chi'\_f(G) \rceil = \chi'(G)$


**Conjecture 3 (new)** For claw-free perfect graphs $\lceil \chi'\_f(G) \rceil = \chi'(G)$


Sage's `fractional_chromatic_index()` is not efficient for me,
is there another implementation?


Counterexamples or proof (especially of (2)) are welcome.


Observe that the question is about **edge coloring**,
not for vertex coloring.



Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index
A result of Cai and Ellis (see Theorem 5 in <http://www.sciencedirect.com/science/article/pii/0166218X9190010T>) implies that deciding whether a cubic perfect line-graph is $3$-edge-colorable is NP-complete. Counter-examples to Conjecture 2 can be built from their argument as follows:


First, notice that every cubic bridgeless graph $G$ satisfies $\chi\_f'(G)=3$. This is easily obtained using the following formula for $\chi\_f'(G)$, which is derived from Edmonds' inequalities for the matching polytope of $G$:
$$\chi\_f'(G)=\max\left(\Delta(G),\max\_{U\subseteq V(G), |U|\geq 3\, \text{odd}}\frac{|E(U)|}{\frac{|U|-1}{2}}\right).$$


Now, consider the following construction: let $H$ be a bridgeless cubic graph and $S(H)$ be the graph obtained from $H$ by subdividing each edge exactly once. Let $G$ be the line graph of $S(H)$.


It is straightforward to check that $G$ is cubic, bridgeless and that: $\chi'(G)=3$ if and only if $\chi'(H)=3$. Furthermore, $G$ is perfect because $S(H)$ is bipartite. 


Therefore, if $H$ is a cubic bridgeless graph with $\chi'(H)=4$ (for example the Petersen graph or any other *snark* [http://en.wikipedia.org/wiki/Snark\_(graph\_theory)](http://en.wikipedia.org/wiki/Snark_%28graph_theory%29)), then $G$ is a cubic bridgeless perfect line-graph with $\chi'(G)>\lceil\chi\_f'(G)\rceil$.


