An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
SIAM Journal on Algebraic and Discrete Methods1981Vol. 2(2), pp. 88–93
Citations Over Time
Abstract
A graph is a circular arc graph if each vertex of the graph is associated with an arc on a circle in such a way that two vertices of the graph are adjacent if and only if the corresponding arcs overlap. A circular arc graph is proper if none of the representing arcs is contained within another. An $O(n^2 )$ algorithm is given for determining whether a proper circular arc graph with n nodes may be colored with k colors.
Related Papers
- Graph Coloring and Its Applications(2019)
- → Vertex-Distinguishing Edge Colorings Of Some Complete Multipartite Graphs(2022)1 cited
- → A hybrid parallel genetic algorithm approach for graph coloring(2005)
- [r, s, t]-coloring of the joint graph C m ∨ C n(2011)
- → Chapter 5 Vertex-Coloring(1988)