Graphs and Matroids Seminar- James Davies ** Rescheduled**

Title: Circle graphs are quadratically x-bounded

Abstract: A circle graph $G$ is an intersection graph of a set of chords on a circle. If there exists a chord diagram of $G$ such that all chords intersect a single additional chord, then $G$ is a permutation graph.

We prove that the vertices of a circle graph $G$ with clique number $k$ can be partitioned into $k+2\lceil 2\log_2(k)\rceil + 4$ sets, each of which induce a permutation graph.  As permutation graphs are perfect this implies that $\chi(G)\le k^2+2k\lceil 2\log_2(k)\rceil + 4k$. Joint work with Rose McCarty.