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 O(n log n) time.
Original language | English (US) |
---|---|
Pages (from-to) | 351-368 |
Number of pages | 18 |
Journal | Algorithmica (New York) |
Volume | 50 |
Issue number | 3 |
DOIs | |
State | Published - Feb 2008 |
Keywords
- Algorithm
- Edge-coloring
- Linear-time
- Planar graph
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics