New Linear-Time Algorithms for Edge-Coloring Planar Graphs |
| |
Authors: | Richard Cole Łukasz Kowalik |
| |
Affiliation: | (1) Computer Science Department, New York University, 251 Mercer Street, New York, NY 10012, USA;(2) Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warsaw, Poland |
| |
Abstract: | 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
time.
R. Cole supported in part by NSF grants CCR0105678 and CCF0515127 and IDM0414763.
Ł. Kowalik supported in part by KBN grant 4T11C04425. Part of this work was done while Ł. Kowalik was staying at the Max Planck
Institute in Saarbruecken, Germany. |
| |
Keywords: | Edge-coloring Linear-time Algorithm Planar graph |
本文献已被 SpringerLink 等数据库收录! |
|