Minimal Universal Bipartite Graphs

Abstract

A graph $U$ is (induced)-universal for a class of graphs $X$ if every member of $X$ is contained in $U$ as an induced subgraph. We study the problem of finding universal graphs with minimum number of vertices for various classes of bipartite graphs: exponential classes, bipartite chain graphs, bipartite permutation graphs, and general bipartite graphs. For exponential classes and general bipartite graphs we present a construction which is asymptotically optimal, while for the other classes our solutions are optimal in order.