加载中…
A classical vertex Ramsey result due to Nešetřil and Rödl states that given a finite family of graphs , a graph and a positive integer , if every graph has a -vertex-connected subgraph which is not a subgraph of , then there exists an -free graph which is vertex -Ramsey with respect to . We prove that this sufficient condition for the existence of an -free graph which is vertex -Ramsey with respect to is also necessary for large enough number of colours . We further show a generalisation of the result to a family of graphs and the typical existence of such a subgraph in a dense binomial random graph.

生成讲解博客的中文版本

生成AI智能校验的中文版本