Covering and coloring polygon-circle graphs

Alexandr Kostochka, Jan Kratochvíl

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)299-305
Number of pages7
JournalDiscrete Mathematics
Volume163
Issue number1-3
DOIs
StatePublished - Jan 15 1997
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Covering and coloring polygon-circle graphs'. Together they form a unique fingerprint.

  • Cite this