Improved bounds for colouring circle graphs

We prove the first $χ$-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 $ω$ has chromatic number at most $2ω\log_2 (ω) +2ω\log_2(\log_2 (ω)) + 10ω$.

No reviews yet.

No comments yet.