Coloring clean and K4-free circle graphs

Alexandr V. Kostochka, Kevin G. Milans

Research output: Chapter in Book/Report/Conference proceedingChapter


A circle graph is the intersection graph of chords drawn in a circle. The best-known general upper bound on the chromatic number of circle graphs with clique number k is 50 · 2k. We prove a stronger bound of 2k-1 for graphs in a simpler subclass of circle graphs, called clean graphs. Based on this result, we prove that the chromatic number of every circle graph with clique number at most 3 is at most 38.

Original languageEnglish (US)
Title of host publicationThirty Essays on Geometric Graph Theory
Number of pages16
ISBN (Electronic)9781461401100
ISBN (Print)1461401097, 9781461401094
StatePublished - Jul 1 2013

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Coloring clean and K<sub>4</sub>-free circle graphs'. Together they form a unique fingerprint.

Cite this