| Thursday 21 November 2024 | |
| Events for day: Wednesday 06 November 2024 |
| 14:00 - 15:00 Combinatorics and Computing Weekly Seminar Chi-boundedness and Exclusion of Complete Graphs School MATHEMATICS The connection between excluding complete graphs (for various notions of exclusion) and the chromatic number of graphs is nearly a century old. In the 1940s, Hadwiger conjectured that a graph with no $K_n$-minor is $(n-1)$-colorable. Later, in the 1950s, Hajos proposed a strengthening of this conjecture, that every graph containing no subdivision of $K_n$ as a subgraph, is $(n-1)$-colorable. While both conjectures remain unresolved in some cases, a bound $c=c(n)$ (instead of $n-1$) for the chromatic number is known for every $n$ for both conjectures. A natural attempt to strengthen this result would be to ask whether there exists a ... |