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:

This entry was posted on Tuesday, April 16th, 2019 at 5:13 am and is filed under 2019, KAIST Discrete Math Seminar. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.