Geodesic
An attractive class of bipartite graphs
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 293-301.

Voir la notice de l'article provenant de la source Library of Science

In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.
Keywords: bipartite graphs, structural characterization, polynomial algorithm 
@article{DMGT_2001_21_2_a12,
     author = {Boliac, Rodica and Lozin, Vadim},
     title = {An attractive class of bipartite graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {293--301},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a12/}
}
TY  - JOUR
AU  - Boliac, Rodica
AU  - Lozin, Vadim
TI  - An attractive class of bipartite graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 293
EP  - 301
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a12/
LA  - en
ID  - DMGT_2001_21_2_a12
ER  - 
%0 Journal Article
%A Boliac, Rodica
%A Lozin, Vadim
%T An attractive class of bipartite graphs
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 293-301
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a12/
%G en
%F DMGT_2001_21_2_a12
Boliac, Rodica; Lozin, Vadim. An attractive class of bipartite graphs. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 293-301. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a12/

[1] V.E. Alekseev, A polynomial algorithm for finding maximum stable sets in fork-free graphs, Discrete Analysis and Operations Research, Ser.1, 6 (4) (1999) 3-19 (in Russian).

[2] A. Brandstädt, The jump number problem for biconvex graphs and rectangle covers of rectangular regions, Lecture Notes in Computer Science 380 (1989) 68-77, doi: 10.1007/3-540-51498-8₇.

[3] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989) 97-102, doi: 10.1016/0166-218X(92)90275-F.

[4] G. Chaty and M. Chein, Ordered matchings and matchings without alternating cycles in bipartite graphs, Utilitas Mathematica 16 (1979) 183-187.

[5] E. Dahlhaus, The computation of the jump number of convex graphs, Lecture Notes in Computer Science 831 (1994) 176-185, doi: 10.1007/BFb0019434.

[6] G. Fricke and R. Laskar, Strong matchings on trees, Congr. Numer 89 (1992) 239-243.

[7] M.C. Golumbic and M. Lewenstein, New results on induced matchings, Discrete Appl. Math. 101 (2000) 157-165, doi: 10.1016/S0166-218X(99)00194-8.

[8] A. Kötzig, Paare Hajös the Graphen, Casopis Pest. Mat. 88 (1963) 236-241.

[9] H. Müller, Alternating cycle free matchings in chordal bipartite graphs, Order 7 (1990) 11-21, doi: 10.1007/BF00383169.

[10] G. Steiner and L. Stewart, A linear time algorithm to find the jump number of 2-dimensional bipartite orders, Order 3 (1987) 359-367, doi: 10.1007/BF00340778.

[11] M. Zito, Linear time maximum induced matching algorithm for trees, Nordic J. Computing 7 (2000) 58-63.