New linear-time algorithms for edge-coloring planar graphs

Richard Cole, Łukasz Kowalik

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)351-368
Number of pages18
JournalAlgorithmica (New York)
Volume50
Issue number3
DOIs
StatePublished - Feb 2008

Keywords

  • Algorithm
  • Edge-coloring
  • Linear-time
  • Planar graph

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'New linear-time algorithms for edge-coloring planar graphs'. Together they form a unique fingerprint.

Cite this