5
$\begingroup$

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,...?

$\endgroup$
6
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is the density of Bipartite chordal graphs I.e. Bipartite graphs such that all cycles of (even) length 6 or more have a chord? I guess in that sense both chordal and bounded tree width graphs will be biparted? $\endgroup$ – SamiD May 23 '15 at 4:09
  • 1
    $\begingroup$ But chordal bipartite graphs in that sense are not a subclass of the chordal graphs. And how does this change the bounded treewidth example in my answer? $\endgroup$ – David Eppstein May 23 '15 at 5:21
  • $\begingroup$ Sorry for not being clear. You are correct that chordal Bipartite graphs are not a subclass of Chordal graphs. My question was if we slightly modify the definition of biparted to compare Chordal and Chordal Bipartite densities then will there be a difference. But here again (at least for bounded tree width) the question does not have a positive answer, as the case of $K_{n-k,k}$ shows. So you were correct on all fronts. $\endgroup$ – SamiD May 23 '15 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.