Improved bounds for colouring circle graphs
James Chowning Davies · Proceedings of the American Mathematical Society · 2022
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 ω log 2 ( ω ) + 2 ω log 2 ( log 2 ( ω ) ) + 10 ω 2\omega \log _2 (\omega ) +2\omega \log _2(\log _2 (\omega )) + 10\omega .