A Ramsey-type theorem for traceable graphs☆
A Ramsey-type theorem for traceable graphs☆
复制标题
可追踪图的拉姆齐型定理☆
DOI：
10.1016/0095-8956(82)90053-3
复制
发表时间：
1982
期刊：
影响因子：
--
通讯作者：
B. Sands
中科院分区：
文献类型：
--
作者：
F. Galvin;I. Rival;B. Sands
如果有一条路径经过g的所有顶点，那么就是一个graphgistrable。证明了每一个无限可迹图要么包含任意大的有限无弦路径，要么包含一个与图a同构的子图，如本文所示。一个推论是，每一个有限生成的长度为3的无限晶格都包含任意大的有限栅栏。并证明了每一个不含无弦四点路径的无限可迹图都包含一个同构于Kω，ω的子图。讨论了这些结果在有限图上的不同版本。
A graphGistraceableif there is a path passing through all the vertices ofG. It is proved thatevery infinite traceable graph either contains arbitrarily large finite chordless paths, or contains a subgraph isomorphic to graph A, illustrated in the text. A corollary is thatevery finitely generated infinite lattice of length3contains arbitrarily large finite fences. It is also proved thatevery infinite traceable graph containing no chordless four-point path contains a subgraph isomorphic to Kω,ω. The versions of these results for finite graphs are discussed.