New Linear-Time Algorithms for Edge-Coloring Planar Graphs

摘要

We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree △ with max{△, 9} colors. Thus the coloring is optimal for graphs with maximum degree △ ≥ 9. Moreover for △ = 4, 5,6 we give linear-time algorithms that use △ + 2 colors. These results improve over the algorithms of Chrobak and Yung (J. Algorithms 10:35-51, 1989) and of Chrobak and Nishizeki (J. Algorithms 11:102-116, 1990) which color planar graphs using max{△, 19} colors in linear time or using max{△, 9} colors in O{n log n) time.