A Ramsey-type theorem for traceable graphs |
| |
Authors: | F Galvin I Rival B Sands |
| |
Institution: | 1. University of Kansas, Lawrence, Kansas 66045, USA;2. University of Calgary, Calgary, Alberta T2N 1N4, Canada |
| |
Abstract: | A graph G is traceable if there is a path passing through all the vertices of G. It is proved that every 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 that every finitely generated infinite lattice of length 3 contains arbitrarily large finite fences. It is also proved that every 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|