New linear-time algorithms for edge-coloring planar graphs

DOI10.1007/s00453-007-9044-3zbMath1141.68050OpenAlexW2158484957WikidataQ56390634 ScholiaQ56390634MaRDI QIDQ2479530

Łukasz Kowalik, Richard John Cole

Publication date: 3 April 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9044-3

zbMATH Keywords

AlgorithmPlanar graphEdge-coloringLinear-time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A Planar linear arboricity conjecture ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ Complexity and algorithms for injective edge-coloring in graphs ⋮ Total tessellation cover: bounds, hardness, and applications

Cites Work

• Unnamed Item
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors
• A simple algorithm for edge-coloring bipartite multigraphs
• 4-edge-coloring graphs of maximum degree 3 in linear time
• Planar graphs of maximum degree seven are Class I
• Improved edge-coloring algorithms for planar graphs
• On the total coloring of planar graphs.
• Fast algorithms for edge-coloring planar graphs

This page was built for publication: New linear-time algorithms for edge-coloring planar graphs