pith. sign in

arxiv: 1503.08258 · v1 · pith:H5AD7F6Vnew · submitted 2015-03-28 · 🧮 math.CO

Excluding long paths

classification 🧮 math.CO
keywords graphsinfinitesubgraphcontainsdingedgeseveryexcluding
0
0 comments X
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.