Edge Coloring (EC)
Input
An undirected graph $G = (V, E)$ with maximum degree $\Delta$.
Problem
Find an edge coloring of $G$ that uses less than or equal to $\Delta + 1$ colors.
Definitions
An edge coloring is an assignment of colors to the edges such that no incident edges receive the same color.
Status
Open (Karloff and Shmoys [1]).
Remarks
An $\NC$ algorithm is known for polylogarithmic $\Delta$ [1]. Karloff and Shmoys give an $\mathsf{RNC}$ algorithm on the COMMON CRCW-PRAM that uses $\Delta + 20 \cdot \Delta^{1/2 + \epsilon}$ colors with running time $(\log |V|)^{O(1)}$ and processors $|V|^{O(1)}$, where the running time is for a fixed $\epsilon > 0$ and the processor bound is independent of $\epsilon$. Also see Problems LFDVC and ER.
Recently, the distributed version of this problem has been widely studied [2]. However, the parallel hardness of this problem remains open [3].
References
- H. J. Karloffand D. B. Shmoys (1987). Efficient parallel algorithms for edge coloring problems.
- A. Bernshteyn and A. Dhawan (2025). Fast algorithms for Vizing’s theorem on bounded degree graphs.
- A. Bernshteyn and A. Dhawan (2026). Efficient Parallel (Δ + 1)-Edge-Coloring (preprint).
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem B.9.3.