𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Improved induced matchings in sparse graphs

✍ Scribed by Rok Erman; Łukasz Kowalik; Matjaž Krnc; Tomasz Waleń

Book ID
108112899
Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
275 KB
Volume
158
Category
Article
ISSN
0166-218X

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.

Induced matchings in cubic graphs
Induced matchings in cubic graphs
✍ Peter Horák; He Qing; William T. Trotter 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 527 KB

## Abstract In this paper, we show that the edge set of a cubic graph can always be partitioned into 10 subsets, each of which induces a matching in the graph. This result is a special case of a general conjecture made by Erdös and Nešetřil: For each __d__ ≥ 3, the edge set of a graph of maximum de

Induced matchings in bipartite graphs
Induced matchings in bipartite graphs
✍ R.J. Faudree; A. Gyárfas; R.H. Schelp; Zs. Tuza 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 454 KB
Maximum matchings in sparse random graph
Maximum matchings in sparse random graphs: Karp–Sipser revisited
✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 490 KB 👁 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3