Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G's bipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree eta(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d less than or equal to 2, and investigate the forbidden graphs for d less than or equal to n that have the fewest vertices. We note that for complete graphs, d(K-n) = [log(2)n], eta(K-n) = d(K-n) for n less than or equal to 16, and eta(K-n) is unbounded. The list of minimal forbidden induced subgraphs for eta less than or equal to 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.