Graphs and Matroids Seminar - Luke PostleExport this event to calendar

Thursday, March 12, 2020 4:00 PM EDT

Title: Improving the general upper bound for Hadwiger's conjecture

Speaker: Luke Postle
Affiliation: University of Waterloo
Room: MC 5479

Abstract:

In 1943, Hadwiger conjectured that every K_t-minor-free graph has chromatic number at most t-1. Hadwiger proved his conjecture for t at most 4, while Wagner showed that the t=5 case is equivalent to the Four Color Theorem, which was later proved by Appel and Haken. In 1993, Robertson, Seymour and Thomas proved the conjecture when t=6.

Until recently, the best known upper bound on the chromatic number of K_t-minor-free graphs was O(t (log t)^(1/2)) which follows from the average degree bounds of Kostochka and Thomason. In a recent breakthrough, Norin and Song improved this to O(t (log t)^0.354). 

We improve on their argument by showing that a graph has a small dense subgraph or a minor of desired density in a way that is essentially asymptotically best possible. This result in conjunction with the work of Norin and Song is used to prove an upper bound for the chromatic number of K_t-minor-free graphs of O(t (log t)^(1/4+epsilon)) for any epsilon > 0.

Location 
MC - Mathematics & Computer Building
5479
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 (147)
    1. December (7)
    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)