Title: Circle graphs are quadratically x-bounded
|Affiliation:||University of Waterloo|
|Room:||**New Room** MC 5501|
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.
200 University Avenue West
Waterloo, ON N2L 3G1