Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
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.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.