报告题目：Hadwiger's conjecture for the complements of Kneser graphs

报告摘要：Hadwiger's conjecture asserts that every graph with chromatic number $t$ contains a complete minor of order $t$. A stronger conjecture due to Haj\'os asserts that every graph with chromatic number $t$ contains a subdivision of $K_{t}$. Haj\'os' conjecture fails for every $t \ge 7$, and if Hadwiger's conjecture is false then counterexamples must be found

among counterexamples to Haj\'os' conjecture. In 2005, Thomassen presented several new classes of counterexamples to Haj\'os' conjecture, including the complements of the Kneser graphs $K(3k-1, k)$ for sufficiently large $k$.

% (Given $n \ge 2k+1 \ge 5$, the Kneser graph $K(n, k)$ is the graph with vertices the $k$-subsets of an $n$-set such that two vertices are adjacent if and only if the corresponding $k$-subsets are disjoint.)

We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.

In the case when $2k+1 \le n \le 3k-1$, the independence number of the complement of $K(n,k)$ is equal to $2$, and we show that the gap between the Hadwiger number and the chromatic number can be arbitrarily large when $n$ and $k$ vary. In general, Hadwiger's conjecture for graphs of independence number 2 is an interesting but challenging problem.

报告人：Guangjun Xu

Zunyi Normal University

(Joint work with Sanming Zhou, The University of Melbourne, Australia)

报告时间：5月26日 上午9:00-10:00

报告地点：数学科学学院38号楼103报告厅

欢迎广大师生参加！