Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
DOI10.1137/0607016zbMATH Open0582.05026OpenAlexW2012615778WikidataQ56235008 ScholiaQ56235008MaRDI QIDQ3705474FDOQ3705474
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
Recommendations
chromatic numberouterplanar graphchromatic indexassociated tree structurebreadth-first coloring algorithm
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Every planar map is four colorable. I: Discharging
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
- Improving the performance guarantee for approximate graph coloring
- On the chromatic index of outerplanar graphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
- Minimum dominating cycles in outerplanar graphs
- Linear algorithms for edge-coloring trees and unicyclic graphs
Cited In (18)
- Graph classes and Ramsey numbers
- A linear-time certifying algorithm for recognizing generalized series-parallel graphs
- Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs.
- An \(O(n\log n)\) algorithm for finding edge span of cacti
- A polynomial-time nearly-optimal algorithm for an edge coloring problem in outerplanar graphs
- Parallel O(log n) time edge-colouring of trees and Halin graphs
- Inductive graph invariants and approximation algorithms
- Title not available (Why is that?)
- An Efficient Algorithm for Generating Colored Outerplanar Graphs
- One-bend drawings of outerplanar graphs inside simple polygons
- The maximum \(k\)-differential coloring problem
- Vertex-coloring with star-defects
- Max point-tolerance graphs
- Optimally edge-colouring outerplanar graphs is in NC
- A heuristic for the coloring of planar graphs
- A \(9k\) kernel for nonseparating independent set in planar graphs
- Backbone colouring: tree backbones with small diameter in planar graphs
- The complexity of pebbling reachability and solvability in planar and outerplanar graphs
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)
