Gallai-Milgram properties for infinite graphs (Q1191912)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Gallai-Milgram properties for infinite graphs |
scientific article |
Statements
Gallai-Milgram properties for infinite graphs (English)
0 references
27 September 1992
0 references
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.
0 references
path-covering
0 references
infinite digraph
0 references
Gallai-Milgram theorem
0 references