|
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, Haj\os 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 constant $c=c(n)$ such that every graph with no subdivision of $K_n$ as an induced subgraph is $c$-colorable. This question is a special case of Scott's conjecture from the 1990s. It was not until 2012 that the first non-trivial case, for $n=4$, was solved by L\ev\^eque, Maffray, and Trotignon.
In this talk, we present the solution to conjecture for $n\geq 5$ and describe the techniques used to achieve this result. This talk is based on joint works with Nicolas Trotignon, particularly the following: arXiv:2112.11970.
Zoom room information:
https://us06web.zoom.us/j/85237260136?pwd=MFSZoKdmRXAjfaSaBzbf19lTaaKglf.1
Meeting ID: 852 3726 0136
Passcode: 362880
|
|