𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Induced matchings in bipartite graphs

✍ Scribed by R.J. Faudree; A. Gyárfas; R.H. Schelp; Zs. Tuza

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
454 KB
Volume
78
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Special parity of perfect matchings in b
Special parity of perfect matchings in bipartite graphs
✍ Ron Aharoni; Rachel Manber; Bronislaw Wajnryb 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 527 KB

Let G be a bipartite graph in which every edge belongs to some perfect matching, and let D be a subset of its edge set. It is shown that M fl D has the same parity for every perfect matching M if and only if D is a cut, and equivalently if and only. if (G, D) is a balanced signed-graph. This gives n

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

Forbidden induced bipartite graphs
Forbidden induced bipartite graphs
✍ Peter Allen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

## Abstract Given a fixed bipartite graph __H__, we study the asymptotic speed of growth of the number of bipartite graphs on __n__ vertices which do not contain an induced copy of __H__. Whenever __H__ contains either a cycle or the bipartite complement of a cycle, the speed of growth is ${{2}}^{\