Abstract We present an algorithm for optimally edge coloring series parallel graphs. We give a linear time implementation, as well as a parallel implementation, of the algorithm that runs in O (log 3 n ) time using O ( n ) processors. The sequential implementation, which is optimal, improves the best-known algorithm. The parallel implementation of the algorithm is the first known NC algorithm for this problem. The algorithm is based on the ear decomposition of a graph (Y. Maon, B. Schieber, and U. Vishkin, Parallel ear decomposition search (EDS) and ST-Numbering in graphs, Theoret. Comput. Sci. 47 (1986), 277-298). Eppstein (Parallel recognition of series-parallel graphs, Inform. Comput. 98 (1992), 41-55) found that any ear decomposition of a series parallel graph is nested . We show constructively that for every biconnected series parallel graph there exists an open ear decomposition, such that its corresponding tree of ears has an O (log n ) depth, and this ear decomposition contains no ear whose endpoints are connected by a single edge in its parent. This result is used to reduce a match in series parallel graphs into a match in outerplanar graphs, and to establish the edge coloring problem of series parallel graphs in NC.