论文标题
色数的多项式边界。 V.排除半径二的树和完整的多方图
Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph
论文作者
论文摘要
Gyárfás-Sumner的猜想说，对于每个森林$ h $和每个整数$ k $，如果$ g $是$ h $ free，并且不包含$ k $ dertices上的集团，则它具有限制的色度。 （如果不包含$ h $的诱导副本，则图是$ h $的。）Kierstead和Penrice最多可证明这是半径的树，但否则，猜想仅以几种简单的森林类型而闻名。众所周知，如果我们将完整的二分子子图而不是一个集团排除在外：rödl表明，对于每个森林$ h $，如果$ g $是$ h $ - $ h $ - free，则不包含$ k_ {t，t，t} $作为子图，那么它具有限制的彩色编号。在与Sophie Spirkl的早期论文中，我们加强了Rödl的结果，表明对于每个森林$ h $，可以将色数的绑定在$ t $中被视为多项式。 In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree $H$ of radius two and every integer $d\ge 2$, if $G$ is $H$-free and does not contain as a subgraph the complete $d$-partite graph with parts of cardinality $t$, then its chromatic number is at most polynomial in $t$.
The Gyárfás-Sumner conjecture says that for every forest $H$ and every integer $k$, if $G$ is $H$-free and does not contain a clique on $k$ vertices then it has bounded chromatic number. (A graph is $H$-free if it does not contain an induced copy of $H$.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest $H$, if $G$ is $H$-free and does not contain $K_{t,t}$ as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest $H$, the bound on chromatic number can be taken to be polynomial in $t$. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree $H$ of radius two and every integer $d\ge 2$, if $G$ is $H$-free and does not contain as a subgraph the complete $d$-partite graph with parts of cardinality $t$, then its chromatic number is at most polynomial in $t$.
