An O(qn) algorithm to q-color a proper family of circular arcs

DOI10.1016/0012-365X(85)90052-4zbMath0567.68043OpenAlexW2074047667MaRDI QIDQ1060020

Austin Teng, Alan C. Tucker

Publication date: 1985

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(85)90052-4

zbMATH Keywords

shortest path problemminimal arc coloringproper arc coloringshortest-path network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

Periodic assignment and graph colouring ⋮ Unnamed Item ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Intersection graphs of proper subtrees of unicyclic graphs ⋮ Precoloring extension on unit interval graphs ⋮ Circular-arc graph coloring: On chords and circuits in the meeting graph ⋮ Bounding χ in terms of ω and Δ for quasi-line graphs ⋮ Edge-coloring of 3-uniform hypergraphs ⋮ An \(0(n^{1.5})\) algorithm to color proper circular arcs ⋮ Perfect circular arc coloring ⋮ Interval graphs and related topics

Cites Work

• Unnamed Item
• Matrix characterizations of circular-arc graphs
• Structure theorems for some circular-arc graphs
• On a routing problem
• An Efficient Test for Circular-Arc Graphs
• An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords

This page was built for publication: An O(qn) algorithm to q-color a proper family of circular arcs