Decomposition of Graphs into Chains
Carsten Thomassen · Bulletin of the London Mathematical Society · 1986
We establish a result on edge-disjoint paths with prescribed ends in infinite trees and apply this to prove the conjecture of Eggleton and Skilton [1] that any connected graph has a decomposition into chains such that at most one of these is one-way infinite and each vertex is the end-vertex of at most one of the chains and no vertex of infinite degree is such an end-vertex. We also give a necessary and sufficient condition for a graph to have a decomposition into one-way infinite chains.