Maximal tight sets and the Edmonds-Gallai decomposition for matchings
type: Item
instance of: scholarly article
title: Maximal tight sets and the Edmonds-Gallai decomposition for matchings
zbMATH Open document ID: 0608.05064
DOI: 10.1007/BF02579252
author: B. George
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: A set A of vertices of a graph G is matchable if some matching of G saturates all vertices of G, and hypomatchable if all subsets \(A\setminus a\) (a\(\in A)\) are matchable. The Edmonds-Gallai decomposition theorem for matchings in finite graphs asserts the following: Let G be a graph and A the set of those vertices of G which are missed by at least one maximal matchable set in G; let B be the set of all other vertices which are adjacent to A, and C the set of remaining vertices. Then (1) each component of G induced on A is hypomatchable, (2) for any matching M of G which saturates the vertices of some maximal matchable set (a) each \(x\in B\) is matched with a vertex of A, (b) each component induced by A has all but one vertex internally matched by M, and (c) all vertices of C are internally matched by M. The author generalizes this result to a statement about infinite graphs. A tight set A is a matchable set for which every matching saturating the vertices of A has all edges intersecting A internal to A. The closure of a tight set A consists of A together with those vertices all of whose neighbours belong to A. The union of the closures of all tight sets in G is called the kernel of G. The generalization of the Edmonds-Gallai theorem proved here gives a decomposition of the kernel of an arbitrary graph G into sets A, B, and C, with properties similar to those above, except that maximal matchable sets are replaced by maximal tight sets. It turns out that if G has a maximal matchable set (and some infinite graphs don't), then G is its own kernel, and the maximal tight sets are precisely the maximal matchable sets. Therefore the classical Edmonds- Gallai theorem applies to all graphs which have a maximal matchable set. These include, in addition to finite graphs, all locally finite graphs, all countable graphs, and all graphs without infinite paths (this last fact being a result of R. Schmidt). That the Edmonds-Gallai decomposition theorem holds for locally finite g…
reviewed by: Pavol Hell
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 3983221
zbMATH Keywords: Edmonds-Gallai decomposition theorem
zbMATH Keywords: matchings
zbMATH Keywords: infinite graphs
zbMATH Keywords: maximal matchable sets
zbMATH Keywords: maximal tight sets
zbMATH Keywords: locally finite graphs
zbMATH Keywords: infinite paths
MaRDI profile type: Publication
cites work: On an obstruction for perfect matchings
cites work: A generalization of Tutte's 1-factor theorem to countable graphs
cites work: The Edmonds-Gallai decomposition for matchings in locally finite graphs
cites work: Paths, Trees, and Flowers
cites work: Q5508779
cites work: On factorisation of graphs
cites work: On the structure of factorizable graphs
cites work: Q3041246
full work available at URL: https://doi.org/10.1007/bf02579252
OpenAlex ID: W2022990157
description: scientific article; zbMATH DE number 3983221