TOPICS
Search

Circular-Arc Graph


A circular-arc graph is an intersection graph of a finite family of nonempty closed circular arcs on a common circle. Each graph vertex represents an arc, and two distinct vertices are adjacent vertices iff the corresponding arcs intersect (Tucker 1975, Tao 2026).

Every interval graph is a circular-arc graph, by mapping its interval representation onto a proper arc of a circle. The converse fails. For example, cycle graphs of length at least 4 have circular-arc representations but are not interval graphs.

Tao (2026) proved that every finite circular-arc graph G satisfies

 ch(G)=chi(G),

where ch(G) is its choice number and chi(G) is its chromatic number.


See also

Choice Number, Intersection Graph, Interval Graph

Explore with Wolfram|Alpha

References

Tao, R. "List Colouring of Circular-Arc Graphs." 16 Nov 2026. https://arxiv.org/abs/2611.20947v1.Tucker, A. "Coloring a Family of Circular Arcs." SIAM J. Appl. Math. 29, 493-502, 1975. https://doi.org/10.1137/0129040.

Cite this as:

Weisstein, Eric W. "Circular-Arc Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Circular-ArcGraph.html

Subject classifications