On spanned subgraphs of graphs
On spanned subgraphs of graphs
复制标题
关于图的跨越子图
DOI：
--
复制
发表时间：
1977
期刊：
影响因子：
--
通讯作者：
A. Hajnal
中科院分区：
文献类型：
--
作者：
A. Hajnal
本文的目的是证明以下类型的一些定理：我们假设 C 是一类满足某些渐近条件的有限图，即 c 及其补集都很大。然后我们考虑 D 类图，并表明对于所有 GEC 和 ， ，i 与 c 的跨度子图同构，前提是 c 的大小与 x 的大小相比足够大。我们已经在[2]和[3]中考虑了无限图的上述问题。在这些情况下，对 C 元素施加的条件是“拉姆齐类型”。为了解释这个表达式，我们陈述一个非常简单的结果，它隐式包含在[.3]中。命题 1. 令 c > o 为实数。设 C 为图 G 的类，使得 G 及其补集都不包含大小为 lAl=lsl=c log n 的完全二部图 [A,BI，其中 n 是 G 的顶点数。然后，对于每个图 H 和每个 GEC G，如果 n > no(c,IIll)，则包含 i 作为跨接子图。 （事实上，只要 cm 足够小，我们就可以用 nE 代替 c ion 来证明这一点。）我们暂时不知道命题 1 的条件是否可以弱化为以下形式：C 是图 G 的类，使得 G 及其补集都不包含大小为 c log n 的完整图。我们来回答这个问题
The aim of this note is to prove some theorems of the following type : We assume that C is a class of finite graphs satisfying certain assymptotic conditions saying that both c and its complement are large. Then we consider a class D of graphs and show that for all GEC and , , i is isomorphic to a spanned subgraph of c provided the size of c is large enough compared to the size of x. We have already considered problems of the above kind for infinite graphs in [2] and [3]. In those cases the conditions imposed on the elements of C were of "Ramsey type". To explain this expression we state a very easy result which is implicitly contained in [ .3]. PROPOSITION 1. Let c > o be a real number. Let C be the class of graphs G such that neither G nor its complement contains complete bipartite graphs [A,BI of the size lAl=lsl=c log n, where n is the number of vertices of G. Then for each graph H and for each GEC G contains i as a spanned subgraph provided n > no(c,IIll). (In fact we can prove this for nE in place of c io€n provided cm is sufficiently small .) We did not know for a while if the condition of Proposition 1 can be weakened to the following : C is the class of graphs G such that neither G nor its complement contains complete graphs of size c log n. We are going to answer this problem