Covering and coloring polygon-circle graphs

✍ Scribed by Alexandr Kostochka; Jan Kratochvíl

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 348 KB
• Volume: 163
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00344-5

✦ Synopsis

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.