Graphs and Matroids Seminar- James Davies ** Rescheduled**Export this event to calendar

Wednesday, February 13, 2019 — 3:30 PM EST

Title: Circle graphs are quadratically x-bounded

Speaker: James Davies
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.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West
Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
  1. 2019 (18)
    1. February (10)
    2. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)