Efficient Vertex- and Edge-Coloring of Outerplanar Graphs

DOI10.1137/0607016zbMath0582.05026OpenAlexW2012615778WikidataQ56235008 ScholiaQ56235008MaRDI QIDQ3705474

Maciej M. Sysło, Andrzej Proskurowski

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607016

zbMATH Keywords

chromatic numberchromatic indexouterplanar graphassociated tree structurebreadth-first coloring algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

A heuristic for the coloring of planar graphs ⋮ One-bend drawings of outerplanar graphs inside simple polygons ⋮ Parallel O(log n) time edge-colouring of trees and Halin graphs ⋮ Max point-tolerance graphs ⋮ The maximum \(k\)-differential coloring problem ⋮ A \(9k\) kernel for nonseparating independent set in planar graphs ⋮ Backbone colouring: tree backbones with small diameter in planar graphs ⋮ Graph classes and Ramsey numbers ⋮ Inductive graph invariants and approximation algorithms ⋮ Optimally edge-colouring outerplanar graphs is in NC ⋮ The complexity of pebbling reachability and solvability in planar and outerplanar graphs ⋮ Vertex-Coloring with Star-Defects ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Linear algorithms for edge-coloring trees and unicyclic graphs
• Every planar map is four colorable. I: Discharging
• On the chromatic index of outerplanar graphs
• An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
• Improving the performance guarantee for approximate graph coloring
• The NP-Completeness of Edge-Coloring
• Minimum dominating cycles in outerplanar graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs