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.