New Linear-Time Algorithms for Edge-Coloring Planar Graphs (http://www.cs.nyu.edu/cole/papers/edge_col.pdf) 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 opti- mal 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 [1] and of Chrobak and Nishizeki [2] which color planar graphs using max{∆, 19} colors in linear time or using max{∆, 9} colors in O(n log n) time.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
regna![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2012-03-14 05:42 pm (UTC)(no subject)
Date: 2012-03-14 08:06 pm (UTC)(no subject)
Date: 2012-03-14 09:43 pm (UTC)(no subject)
Date: 2012-03-24 01:30 am (UTC)New Linear-Time Algorithms for Edge-Coloring Planar Graphs (http://www.cs.nyu.edu/cole/papers/edge_col.pdf)
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 opti- mal 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 [1] and of Chrobak and Nishizeki [2] which color planar graphs using max{∆, 19} colors in linear time or using max{∆, 9} colors in O(n log n) time.