NP-completeness results for some problems on subclasses of bipartite and chordal graphs

Edge Dominating Sets in Graphs

Mihalis Yannakakis, Fǎnicǎ Gavril · SIAM Journal on Applied Mathematics · 1980 · 388 citations

Graph Minor, Engineering, Graph Theory +14

Bipartite permutation graphs

Jeremy Spinrad, Andreas Brandstädt, Lorna Stewart · Discrete Applied Mathematics · 1987 · 232 citations

Bipartite Permutation Graphs, Graph Theory, Structural Graph Theory +6

Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

Witold Lipski, F. P. Preparata · Acta Informatica · 1981 · 113 citations

Mathematical Programming, Maximum Matchings, Network Science +15

An interpolation theorem for graphical homomorphisms

Frank Harary, Stephen T. Hedetniemi, Geert Prins · Portugaliae Mathematica · 1967 · 102 citations

Interpolation Space, Graph Theory, Algebraic Graph Theory +2

The achromatic number of a graph

F. Harary, Stephen T. Hedetniemi · Journal of Combinatorial Theory · 1970 · 98 citations

Geometric Graph Theory, Graph Theory, Algebraic Graph Theory +3