Gallai-Milgram properties for infinite graphs
type: Item
instance of: scholarly article
title: Gallai-Milgram properties for infinite graphs
zbMATH Open document ID: 0766.05041
DOI: 10.1016/0012-365X(91)90328-Y
author: J.-M. Brochet
author: Maurice Pouzet
published in: Discrete Mathematics
publication date: 1992-09-27T00:00:00Z
review text: 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.
reviewed by: R. E. L. Aldred
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 06A05
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 63127
zbMATH Keywords: path-covering
zbMATH Keywords: infinite digraph
zbMATH Keywords: Gallai-Milgram theorem
MaRDI profile type: Publication
cites work: Normal Tree Orders for Infinite Graphs
cites work: A decomposition theorem for partially ordered sets
cites work: Q3283482
cites work: Set theory.
cites work: On Dilworth's theorem in the infinite case
full work available at URL: 0012-365x(91)90328-y
OpenAlex ID: W2003802984
Wikidata QID: Q127894653
Recommended article: Q3971998
Recommended article: On the Turán properties of infinite graphs
Recommended article: On the girth of infinite graphs
Recommended article: Menger's theorem for infinite graphs
Recommended article: Q3224160
Recommended article: Q3204497
Recommended article: On the metric dimension of infinite graphs
Recommended article: Infinite random graphs and properties of metrics
Recommended article: Extremal infinite graph theory
description: scientific article; zbMATH DE number 63127