University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte Colloquium - Nicolas TrotignonExport this event to calendar

Friday, June 19, 2020 — 3:30 PM EDT

Title: Widths in even-hole-free graphs

Speaker: Nicolas Trotignon
Affiliation: CNRS - LIP - École Normale Supérieure de Lyon
Zoom: Please email Emma Watson

Abstract:

Historically, the study of even-hole-free graphs is motivated by the analogy with perfect graphs. The decomposition theorems that are known for even-hole-free graphs are seemingly more powerful than the ones for perfect graphs: the basic classes and the decompositions are in some respect more restricted. But strangely, in an algorithmic perpective, much more is known for perfect graphs. For instance, coloring and finding a maximum stable set are open for even-hole-free graphs and polytime for perfect graphs. Also, it is very easy to provide perfect graphs of large treewidth and rankwidth, because of all bipartite graphs are perfect. For even-hole-free graphs, it is harder, but there are now several constructions, and the goal of the present talk is to survey all of them. On the way, we will give several open questions motivated by algorithms for even-hole-free graphs.  

Based on joint works with Isolde Adler, Chinh Hoang, Ngoc Khang Le, Haiko Muller, Marko Radovanovic, Ni Luh Dewi Sintiari and Kristina Vuskovic 

S M T W T F S
26
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
29
30
31
1
2
3
4
5
  1. 2020 (74)
    1. August (7)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)