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

DOI10.1137/0602012MaRDI QIDQ3960133zbMATH OpenOpenAlexFDO

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

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)

Cites work

• scientific article; zbMATH DE number 3521893 (Why is no real title available?)
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Coloring a Family of Circular Arcs
• Cyclic Scheduling via Integer Programs with Circular Ones
• Matrix characterizations of circular-arc graphs
• Minimum node disjoint path covering for circular-arc graphs
• On a routing problem
• Structure theorems for some circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(23)

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

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

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