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

DOI10.1137/0602012zbMATH Open0496.68047OpenAlexW1985464850MaRDI QIDQ3960133FDOQ3960133

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

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

Cited In (22)

• 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
• 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)