CANCELLED Tutte Colloquium - Nicolas TrotignonExport this event to calendar

Friday, March 13, 2020 3:30 PM EDT

Title: Widths in even-hole-free graphs

Speaker: Nicolas Trotignon
Affiliation: École Normale Supérieure de Lyon
Room: MC 5501

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 more restricted. But strangely, in an algorithmic perspective, 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 

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

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