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 language||English (US)|
|Title of host publication||Thirty Essays on Geometric Graph Theory|
|Number of pages||16|
|ISBN (Print)||1461401097, 9781461401094|
|State||Published - Jul 1 2013|
ASJC Scopus subject areas