Polygon-circle graphs are intersection graphs of polygons inscribed in a circle. This class of graphs includes circle graphs (intersection graphs of chords of a circle), circular arc graphs (intersection graphs of arcs on a circle), chordal graphs and outerplanar graphs. We investigate binding functions for chromatic number and clique covering number of polygon-circle graphs in terms of their clique and independence numbers. The bound α log α for the clique covering number is asymptotically best possible. For chromatic number, the upper bound we prove is of order 2ω, which is better than previously known upper bounds for circle graphs.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics