Gallai-Milgram properties for infinite graphs (Q1191912)

The Gallai-Milgram theorem states that the vertices of a finite digraph with no independent set of size \(k+1\), can be covered by \(k\) or fewer pairwise disjoint paths. This paper discusses extensions of this result to infinite graphs. The undirected analogue of the Gallai-Milgram theorem is thus obtained. In addition it is shown that if to each edge \((x,y)\) of a countable path an element \(\theta(x,y)\) of a finite group is assigned, then some edges can be deleted so that the new graph is still a path and the product \(\theta(x_ 1,x_ 2)\cdot\theta(x_ 2,x_ 3)\cdot\dots\cdot\theta(x_{n-1},x_ n)\) along any finite path of the new graph depends only upon the endvertices \(x_ 1\) and \(x_ n\). A path in this paper is a directed graph whose transitive closure is a linear ordering.