๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Maximum matchings in planar graphs via gaussian elimination

โœ Scribed by Marcin Mucha; Piotr Sankowski

Publisher
Springer
Year
2006
Tongue
English
Weight
910 KB
Volume
45
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Maximum induced matchings in graphs
Maximum induced matchings in graphs
โœ Jiping Liu; Huishan Zhou ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 218 KB

We provide a formula for the number of edges of a maximum induced matching in a graph. As applications, we give some structural properties of (k + 1 )K2-free graphs, construct all 2K2-free graphs, and count the number of labeled 2K2-free connected bipartite graphs.

Extending matchings in planar graphs IV
Extending matchings in planar graphs IV
โœ Michael D. Plummer ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 973 KB

Plummer, M.D., Extending matchings in planar graphs IV, Discrete Mathematics 109 (1992) 207-219. The structure of certain non-Zextendable planar graphs is studied first. In particular, 4-connected S-regular planar graphs which are not 2-extendable are investigated and examples of these are presented

Extending matchings in planar graphs V
Extending matchings in planar graphs V
โœ Michael D. Plummer ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 473 KB

A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges el