IPM

                                پژوهشگاه دانش‌های بنیادی
پژوهشکدهٔ ریاضیات


Combinatorics and Computing Weekly Seminar سمینار هفتگی ترکیبیات و محاسبه




TITLE  
Chi-boundedness and Exclusion of Complete Graphs


SPEAKER  
Pegah Pournajafi  
College de France  
 


TIME  
Wednesday, November 6, 2024,   14:00 - 15:00


VENUE   Lecture Hall 1, Niavaran Bldg.



SUMMARY

 

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

 




تهران، ضلع‌ جنوبی ميدان شهيد باهنر (نياوران)، پژوهشگاه دانش‌های بنيادی، پژوهشکده رياضيات
School of Mathematics, Institute for Research in Fundamental Sciences (IPM), Niavaran Bldg., Niavaran Square, Tehran
ipmmath@ipm.ir   ♦   +98 21 22290928   ♦  math.ipm.ir