Excluding long paths
classification
🧮 math.CO
keywords
graphsinfinitesubgraphcontainsdingedgeseveryexcluding
read the original abstract
Ding (1992) proved that for each integer ${m} \geqslant 0$, and every infinite sequence of finite simple graphs $G_1, G_2, \ldots$, 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.