Improved bounds for colouring circle graphs

James Davies

Published 2021-07-08Version 1

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$.