Efficient Vertex- and Edge-Coloring of Outerplanar Graphs

DOI10.1137/0607016MaRDI QIDQ3705474zbMATH OpenOpenAlexWikidataFDO

Authors Andrzej Proskurowski, Maciej M. Sysło

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

associated tree structurebreadth-first coloring algorithmchromatic indexchromatic numberouterplanar graph

Mathematics Subject Classification ID

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

Recommendations

• A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs
• On the colorings of outerplanar graphs
• Acyclic Edge Colouring of Outerplanar Graphs
• scientific article; zbMATH DE number 432820
• On colorings of squares of outerplanar graphs

Cites work

• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
• Every planar map is four colorable. I: Discharging
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improving the performance guarantee for approximate graph coloring
• Linear algorithms for edge-coloring trees and unicyclic graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Minimum dominating cycles in outerplanar graphs
• On the chromatic index of outerplanar graphs
• The NP-Completeness of Edge-Coloring

Cited in

(20)

• Parallel O(log n) time edge-colouring of trees and Halin graphs
• On the colorings of outerplanar graphs
• A linear-time certifying algorithm for recognizing generalized series-parallel graphs
• A heuristic for the coloring of planar graphs
• One-bend drawings of outerplanar graphs inside simple polygons
• The maximum \(k\)-differential coloring problem
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• Vertex-coloring with star-defects
• An O(n n) algorithm for finding edge span of cacti
• A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs
• scientific article; zbMATH DE number 432820 (Why is no real title available?)
• Max point-tolerance graphs
• 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
• On the cost chromatic number of outerplanar, planar, and line graphs
• Inductive graph invariants and approximation algorithms
• An Efficient Algorithm for Generating Colored Outerplanar Graphs
• Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs.
• Optimally edge-colouring outerplanar graphs is in NC

This page was built for publication: Efficient Vertex- and Edge-Coloring of Outerplanar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3705474)