Improved bounds for colouring circle graphs

Abstract

We prove the first $\chi$-bounding function for circle graphs that is optimal up to a constant factor. To be more precise, we prove that every circle graph with clique number at most $\omega$ has chromatic number at most $2\omega {\log }_2(\omega )+2\omega {\log }_2({\log }_2(\omega ))+10\omega$.