Bipartite matching extendable graphs Original Research Article

Matching extendability is significant in graph theory and its applications. The basic notion in this direction is image-extendability introduced by Plummer in 1980. Motivated by the different natures of bipartite matchings and non-bipartite matchings, this paper investigates bipartite-matching extendable (BM-extendable) graphs. A graph image is said to be BM-extendable if every matching image which is a perfect matching of an induced bipartite subgraph can be extended to a perfect matching. Our main results are showing that the recognition of BM-extendable graphs is co-NP-complete and characterizing some classes of BM-extendable graphs.