论文标题
大连通性和色数的子图
Subgraphs of large connectivity and chromatic number
论文作者
论文摘要
解决Norin提出的问题，我们表明，对于\ Mathbb {n} $中的每个$ k \，存在$ f（k）\ le 7k $，使每个图$ g $具有至少$ f（k）+1 $的每个图形$ g $，包含一个子Graph $ h $，均为连接性和$ k $。该结果最能获得乘法常数，从1987年开始，Alon-Kleitman-Thomassen-Saks-Seymour的早期结果表明，$ f（k）= O（k^3）$，以及Chudnovsky-Penev-Scott-trotignon的2013年$ f（k）= f（k）= o（k）= o（k^2）$。 Our methods are robust enough to handle list colouring as well: we also show that for each $k \in \mathbb{N}$, there exists an $f_\ell(k) \le 4k$ such that every graph $G$ with list chromatic number at least $f_\ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$.这个结果再次是最能力的乘法常数。在这里，与$ f（\ cdot）$不同，即使存在$ f_ \ ell（\ cdot）$的存在似乎以前是未知的。
Resolving a problem raised by Norin, we show that for each $k \in \mathbb{N}$, there exists an $f(k) \le 7k$ such that every graph $G$ with chromatic number at least $f(k)+1$ contains a subgraph $H$ with both connectivity and chromatic number at least $k$. This result is best-possible up to multiplicative constants, and sharpens earlier results of Alon-Kleitman-Thomassen-Saks-Seymour from 1987 showing that $f(k) = O(k^3)$, and of Chudnovsky-Penev-Scott-Trotignon from 2013 showing that $f(k) = O(k^2)$. Our methods are robust enough to handle list colouring as well: we also show that for each $k \in \mathbb{N}$, there exists an $f_\ell(k) \le 4k$ such that every graph $G$ with list chromatic number at least $f_\ell(k)+1$ contains a subgraph $H$ with both connectivity and list chromatic number at least $k$. This result is again best-possible up to multiplicative constants; here, unlike with $f(\cdot)$, even the existence of $f_\ell(\cdot)$ appears to have been previously unknown.
