论文标题
高度连接的子图具有较大的色数
Highly connected subgraphs with large chromatic number
论文作者
论文摘要
对于整数$ k \ ge1 $和$ m \ ge2 $，让$ g（k，m）$是至少整数$ n \ ge1 $，以使每个具有至少$ n $的变色数的图都包含一个$（k+1）$连接的子图，带有至少$ m $的色度。完善最近的结果Girão和Narayanan，所有$ k \ ge2 $ $ g（k-1，k）\ le 7k+1 $，我们证明$ g（k，m）\ le \ max（m+2k-2，\ lceil（3+ \ frac \ frac {1} {1} {1} {16} {16} {16} {16} {16} {16} {16} {16} {16}）这使Chudnovsky，Penev，Scott和Trotignon的Alon，Kleitman，Saks，Seymour和Thomassen以及Penev，Thomassé和Trotignon的早期结果得到了增强。 Our result implies that $g(k,k+1)\le\lceil(3+\frac{1}{16})k\rceil$ for all $k\ge1$, making a step closer towards a conjecture of Thomassen from 1983 that $g(k,k+1)\le 3k+1$, which was originally a result with a false proof and was the starting point of this research area.
For integers $k\ge1$ and $m\ge2$, let $g(k,m)$ be the least integer $n\ge1$ such that every graph with chromatic number at least $n$ contains a $(k+1)$-connected subgraph with chromatic number at least $m$. Refining the recent result Girão and Narayanan that $g(k-1,k)\le 7k+1$ for all $k\ge2$, we prove that $g(k,m)\le \max(m+2k-2,\lceil(3+\frac{1}{16})k\rceil)$ for all $k\ge1$ and $m\ge2$. This sharpens earlier results of Alon, Kleitman, Saks, Seymour, and Thomassen, of Chudnovsky, Penev, Scott, and Trotignon, and of Penev, Thomassé, and Trotignon. Our result implies that $g(k,k+1)\le\lceil(3+\frac{1}{16})k\rceil$ for all $k\ge1$, making a step closer towards a conjecture of Thomassen from 1983 that $g(k,k+1)\le 3k+1$, which was originally a result with a false proof and was the starting point of this research area.
