학과 세미나 및 콜로퀴엄

구분 IBS-KAIST 세미나
분류 이산수학
제목 Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs
Abstract Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139-144] conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all colors in every t-coloring of G, then G contains a $K_t$-minor rooted at S. We prove this conjecture in the first open case of t=4. Notably, our result also directly implies a stronger version of Hadwiger's conjecture for 5-chromatic graphs as follows: Every 5-chromatic graph contains a $K_5$-minor with a singleton branch-set. In fact, in a 5-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph. Joint work with Anders Martinsson (ETH).
일시 2023-02-14 (Tue) / 16:30 ~ 17:30
장소 Room B332, IBS (기초과학연구원)
강연언어 영어
강연자성명 Raphael Steiner
강연자소속 ETH Zürich
강연자홈페이지 https://sites.google.com/view/raphael-mario-steine
기타정보
초청인 Sang-il Oum
URL https://dimag.ibs.re.kr/event/2023-02-14/
담당자
연락처