Excluding long paths

Abstract

Ding (1992) proved that for each integer $m⩾0$, and every infinite sequence of finite simple graphs $G_1,G_2,\dots$, if none of these graphs contains a path of length $m$ as a subgraph, then there are indices $i<j$ such that $G_i$ is isomorphic to an induced subgraph of $G_j$. We generalise this result to infinite graphs, possibly with parallel edges and loops.

9 pages and 1 figure. arXiv admin note: text overlap with arXiv:1405.6527