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.