BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE
Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara · Discrete Mathematics Algorithms and Applications · 2012
The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.