论文标题
诱导的大色数的诱导子图的子图
Induced subgraphs of induced subgraphs of large chromatic number
论文作者
论文摘要
我们证明，对于至少具有一个边缘的每个图形$ f $，都有一个常数$ c_f $，因此有任意大的色度数和与$ f $相同的集团数的图，其中每个$ f $ f $ f $ toctuse tocused submerpraph最多都有$ c_f $的色度。这概括了Briański，Davies和Walczak以及Carbonero，Hompe，Moore和Spirkl的最新定理。我们的结果意味着，每$ r \ geq 3 $ $ k_r $ - free图的类都具有很强的顶点ramsey型属性，从而对1970年的《民俗》的结果进行了广泛的概括。我们还证明了与锦标赛，超graphs和无限族的图形族和图形的类似图表相关的结果，并显示出图形的类似词，由clique quplique quir quir quir qir quir quir qir quir。
We prove that, for every graph $F$ with at least one edge, there is a constant $c_F$ such that there are graphs of arbitrarily large chromatic number and the same clique number as $F$ in which every $F$-free induced subgraph has chromatic number at most $c_F$. This generalises recent theorems of Briański, Davies and Walczak, and Carbonero, Hompe, Moore and Spirkl. Our results imply that for every $r\geq 3$ the class of $K_r$-free graphs has a very strong vertex Ramsey-type property, giving a vast generalisation of a result of Folkman from 1970. We also prove related results for tournaments, hypergraphs and infinite families of graphs, and show an analogous statement for graphs where clique number is replaced by odd girth.
