Premium
An Application of Rado's Theorem to Disjoint Matchings in Bipartite Graphs
Author(s) -
Murty U. S. R.
Publication year - 1978
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-17.2.193
Subject(s) - bipartite graph , disjoint sets , combinatorics , mathematics , strong perfect graph theorem , robertson–seymour theorem , cograph , discrete mathematics , graph , 1 planar graph , chordal graph
For the terminology and notation we follow Bondy and Murty [1] in graph theory and Welsh [3] in matroid theory. All sets considered are finite. Let G be a bipartite graph with bipartition (X, Y) and let V and E denote, respectively, the vertex and edge sets of G. A matching M in G is called a matching of X into Y if every vertex in X is M-saturated. If S is any subset of V, we shall write <5(S) to denote the set of edges incident with S; we simplify 5({y}) to 5(y). Lebensold [2] proved the following result.