Rose McCarty, Circle graphs are polynomially chi-bounded

IBS/KAIST Joint Discrete Math Seminar

Circle graphs are polynomially chi-bounded
Rose McCarty
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 4k2. Joint with James Davies.
Tags: RoseMcCarty

Monthly Archives