An efficient algorithm for edge coloring planar graphs with Δ colors

We present an efficient algorithm for edge coloring a planar graphG. Let n be the number of vertices and Δ be the maximum degree of G. If Δ ≥33, our algorithm constructs an edge coloring of G using Δ colors. The parallel implementation of the algorithm takes O(log2 n) time with O(n) processors. The sequential implementation takes O(n) time.

Authors

• Xin He

Keywords

No keywords are indexed for this paper.