Sparser Bipartite graphs?

Question

Maximal Planar Bipartite graphs are sparser than maximal planar graphs. For which other classes of graphs are maximal Bipartite members sparser than arbitrary maximal members.

Let $\mathcal{C}$ be a class of graphs and let $\mathcal{B}$ be the class of bipartite graphs. We say that $\mathcal{C}$ is biparted if $\rho(\mathcal{C}) > \rho(\mathcal{B}\cap\mathcal{C})$ (where $\rho(\mathcal{C})$ is defined below) i.e. the asymptotic density of arbitrary graphs in the class is larger than the asymptotic density of the bipartite graphs in the same class.

Examples of biparted graphs are:

• Planar Graphs ($\rho(\mathcal{C}) = 6 > 4 = \rho(\mathcal{C}\cap \mathcal{B})$)
• Graphs of finite genus (same parameters as above)
• Subclasses of planar graphs e.g. outerplanar graphs

My question is:

Are there any other natural classes of biparted graphs?

For a graph $G$, let $\rho(G) = \frac{2|E(G)|}{|V(G)|}$ be the average degree of a vertex. We say that a class of graphs $\mathcal{C}$ is maximally $\rho$-sparse - written as $\rho = \rho(\mathcal{C})$ i.e. the maximum of average density (with maximum taken over all graphs from $\mathcal{C}$ with sufficiently many vertices) approaches $\rho$.

Note: Planar graphs can be proved to be biparted because Euler formula holds. The same is the case with bounded genus graphs. What about bounded tree-width graphs, graphs excluding a finite set of fixed minors,...?

Answer 1

For an extreme example, chordal graphs can have as many as $\binom{n}{2}$ edges but chordal graphs that happen to also be bipartite can have only $n-1$ edges (they are forests). Or even more extremely, consider complete graphs versus (complete $\cap$ bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are naturally sparse, as the planar and minor-closed graph families are.

It is not true that all minor-closed families are biparted; in particular, the graphs of treewidth $k$ are not. An $n$-vertex graph with treewidth $k$ has at most $\binom{k}{2}+k(n-k)$ edges, but (for large $n$ and small $k$) the complete bipartite graph $K_{n-k,k}$ has treewidth $k$ and is almost as dense with $k(n-k)$ edges.

One can extend the bounds from planar graphs to $k$-apex graphs (graphs such that you can delete $k$ vertices and get a planar graph), and their generalization to $(g,k)$-apex graphs for bounded genus $g$: these graphs have at most $(k+3)n+O(g)$ edges but their bipartite subclasses have at most $(k+2)n+O(g)$.

Moving beyond minor-closed properties but continuing with graphs related to planar graphs, the 1-planar graphs (graphs that can be drawn with at most one crossing per edge) can have at most $4n-8$ edges, but bipartite 1-planar graphs can have at most $3n-6$. See Czap and Hudák, "On drawings and decompositions of 1-planar graphs", Elect. J. Comb. 2013. And the graphs with book thickness $k$ have at most $(k+1)n-O(1)$ edges ($2n-3$ for the first page and $n-3$ for each subsequent page), but when they are bipartite the constant factor is lower because the first page is outerplanar. I suspect that similar things happen with other types of almost-planar graph.