Author(s)

Ruzayn Quaddoura^*

Department of Computer Science, Faculty of Information Technology, Zarqa University, Zarqa, Jordan.

The bipartite Star₁₂₃-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star₁₂₃-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star₁₂₃, P₇-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.

Bipartite Graphs, Decomposition of Graphs, Design and Analysis of Algorithms, Matching

Quaddoura, R. (2016) Solving the Maximum Matching Problem on Bipartite Star₁₂₃-Free Graphs in Linear Time. Open Journal of Discrete Mathematics, 6, 13-24. doi: 10.4236/ojdm.2016.61003.