David Eppstein, Giuseppe F Italiano, et al.
Journal of Algorithms
We present two algorithms which color edges of every planar graph G with max(Δ(G), 19) colors. Therefore both algorithms produce an optimal coloring if Δ(G) ≥ 19. The first one is a linear-time sequential algorithm. The second one is a parallel EREW PRAM algorithm which runs in O(log2n) time using O(n) processors. Both algorithms are based on reduction techniques analogous to techniques used previously for vertex coloring, and both improve the best known sequential and parallel algorithms. The results are generalized to constant-genus graphs. © 1989.
David Eppstein, Giuseppe F Italiano, et al.
Journal of Algorithms
Bülent Yener, Yoram Ofek, et al.
IEEE/ACM Transactions on Networking
Xiangdong Yu, Moti Yung
Theoretical Computer Science
Yehuda Afek, Gad M. Landau, et al.
Information and Computation