1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.