**Combinatorics and Computing Weekly Seminar**

Chi-boundedness and Exclusion of Complete Graphs

Pegah Pournajafi, College de France

6 NOV 2024

14:00 - 15:00

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 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 Lev^eque, Maffray, and Trotignon.

In this talk, we present the solution to conjecture for $ngeq 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

**Venue**: Niavaran, Lecture Hall 1