# complexity of computing fractional edge-chromatic number of an edge-weighted graph

Let $$(G,w)$$ be an edge-weighted graph, where the weights $$w(e)$$ are assumed to be rational. My question is: What is the complexity of computing $$\chi'_f(G,w)$$, the fractional edge-chromatic number of $$(G,w)$$, denoted by $$\chi'_f(G,w)$$.

Let $$M$$ be the edge-matching incidence matrix of $$G$$. Thus, $$M_{ij} = 1$$ iff the $$i$$th edge belongs to the $$j$$th matching. Then, $$\chi'_f(G,w)$$ can be defined to be the value of the linear program: $$\min 1^T x$$ subject to $$Mx \ge w, x \ge 0$$.

A formula for this value is given by Edmond's matching polytope theorem: Let $$\Delta(G)$$ denote the maximum sum of the weights of edges incident to a vertex, i.e $$\Delta(G) = \max_{v \in V(G)} \sum_{e: e \sim v} w(e)$$ Let $$\Lambda(G) = \max_{H \subseteq G} \frac{2|E(H,w)|}{|V(H)|-2}$$, where the maximum is over all induced subgraphs $$H$$ of $$G$$ of odd order, and $$|E(H,w)|$$ denotes the sum of the weights of edges in $$H$$. By Edmond's matching polytope theorem, $$\chi'_f(G,w) = \max\{\Delta(G), \Lambda(G) \}$$.

Computing the edge-chromatic number $$\chi'(G)$$, vertex-chromatic number $$\chi(G)$$, and fractional chromatic number $$\chi_f(G)$$, are all NP-hard. From what I've read, it seems $$\chi'_f(G)$$ can be computed in polynomial time, even though the number of matchings (or number of induced subgraphs $$H$$) can be exponential, by solving a maximum weighted matching problem, which has complexity $$O(n^4)$$ or better. Also, I'm interested mainly in the edge-weighted case.