IBS/KAIST Joint Discrete Math Seminar

Circle graphs are polynomially chi-bounded

Rose McCarty

University of Waterloo, Waterloo, Canada

University of Waterloo, Waterloo, Canada

2019/04/26 Fri 4PM-5PM (IBS, Room B232)

Circle graphs are the intersection graphs of chords on a circle; vertices correspond to chords, and two vertices are adjacent if their chords intersect. We prove that every circle graph with clique number k has chromatic number at most 4k

^{2}. Joint with James Davies.