## Abstract

An edge of a graph is light when the sum of the degrees of its end-vertices is at most 13. The well-known Kotzig theorem states that every 3-connected planar graph contains a light edge. Later, Borodin [J. Reine Angew. Math., 394 (1989), pp. 180-185] extended this result to the class of planar graphs of minimum degree at least 3. We deal with generalizations of these results for planar graphs of minimum degree 2. Borodin, Kostochka, and Woodall [J. Combin. Theory Ser. B, 71 (1997), pp. 184-204] showed that each such graph contains a light edge or a member of two infinite sets of configurations, called 2-alternating cycles and 3-alternators. This implies that planar graphs with maximum degree Δ > 12 are Δ-edge-choosable. We prove a similar result with 2-alternating cycles and 3-alternators replaced by five fixed bounded-sized configurations called crowns. This gives another proof of Δ-edge-choosability of planar graphs with Δ > 12. However, we show efficient choosability; i.e., we describe a linear-time algorithm for max{Δ, 12}-edge-list-coloring planar graphs. This extends the result of Chrobak and Yung [J. Algorithms, 10 (1989), pp. 35-51].

Original language | English (US) |
---|---|

Pages (from-to) | 93-106 |

Number of pages | 14 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 21 |

Issue number | 1 |

DOIs | |

State | Published - 2007 |

## Keywords

- Algorithm
- Choosability
- Kotzig's theorem
- Light edge
- List-coloring
- Planar graph

## ASJC Scopus subject areas

- Mathematics(all)