An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs

DOI10.1137/0602012zbMath0496.68047OpenAlexW1985464850MaRDI QIDQ3960133

Maurizio A. Bonuccelli, Daniel P. Bovet, James B. Orlin

Publication date: 1981

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

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

Mathematics Subject Classification ID

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

Related Items (22)

Periodic assignment and graph colouring ⋮ Some parallel algorithms on interval graphs ⋮ Unnamed Item ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ The complexity of colouring circle graphs ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ The complexity of path coloring and call scheduling ⋮ Precoloring extension on unit interval graphs ⋮ Minimum sum edge colorings of multicycles ⋮ Circular-arc graph coloring: On chords and circuits in the meeting graph ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ An \(0(n^{1.5})\) algorithm to color proper circular arcs ⋮ Perfect circular arc coloring ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ An O(qn) algorithm to q-color a proper family of circular arcs ⋮ Interval graphs and related topics ⋮ On a packet scheduling problem for smart antennas and polyhedra defined by circular-ones matrices ⋮ Dominating sets and domatic number of circular arc graphs

Cites Work

• Unnamed Item
• Minimum node disjoint path covering for circular-arc graphs
• Matrix characterizations of circular-arc graphs
• Structure theorems for some circular-arc graphs
• On a routing problem
• Cyclic Scheduling via Integer Programs with Circular Ones
• An Efficient Test for Circular-Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• Coloring a Family of Circular Arcs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs