Using the minimum maximum flow degree to approximate the flow coloring problem

Consider an arc-capacitated network $$\mathcal {N}$$ N through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multigraph with the same vertices as $$\mathcal {N}$$ N and an edge for each arc of $$\mathcal {N}$$ N , where the edge multiplicity is the flow in the respective arc. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of $$\mathcal {N}$$ N , i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining on $$\mathcal {N}$$ N a feasible flow such that its maximum flow degree is minimum. We present a polynomial time algorithm for this problem. We use its optimum value to derive an improved upper bound for the flow coloring problem (FCP), which consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index. Based on this procedure, we design an approximation algorithm for the FCP that improves the best known approximation factor.