Coloring circle graphs

Circle graph is an intersection graph of chords of a circle. We denote the class of circle graphs by cir. In this paper we investigate the chromatic number of the circle graph as a function of the size of maximum clique ω=ω(G). More precisely we investigate f(k)=max{χ(G)|G∈CIR &ω(G)⩽k}. Kratochvíl and Kostochka showed that f(k)⩽50⋅k2−32k−64. The best lower bound is by Kostochka and is f(k)=Ω(klogk). We improve the upper bound to f(k)⩽21⋅k2−24k−24. We also present the bound χ(G)⩽ω⋅logn which shows, that the circle graphs with small maximum clique and large chromatic number must have many vertices.