6
$\begingroup$

I would like to compile a list of questions about graphs that have a non-trivial analogs for bipartite graphs.

Let me give the following examples:

  1. Cycle vs Even cycle. Most questions about cycles in graphs have analogs in even cycles for bipartite graphs. For instance, it is trivial to show that a bipartite graph on an odd number of vertices cannot have a Hamilton cycle. In such a case the bipartite analog of a Hamilton cycle is a cycle missing exactly one vertex.

  2. Minimal Girth. For graphs, 3 is the minimal possible length of a cycle. For bipartite graphs, the analogous number is 4.

  3. Triangular vs quadrangular embeddings. In topological graph theory, a triangular embedding of a simple graph determine its genus. For bipartite graphs, the analog is an embedding with quadrangles as faces.

$\endgroup$
1
  • $\begingroup$ I think there are various interesting examples. I cannot think of them from the top of my head but I plan to return to it. Good question! (I didnt see the point of item 2 though.) $\endgroup$
    – Gil Kalai
    Mar 8, 2010 at 22:23

3 Answers 3

6
$\begingroup$

There's a standard combinatorial equivalence between undirected bipartite graphs and general directed graphs: just use the biadjacency matrix of the bipartite graph as an adjacency matrix of the directed graph and vice versa. See: R. A. Brualdi, F. Harary, , and Z. Miller (1980), "Bigraphs versus digraphs via matrices", Journal of Graph Theory 4 (1): 51–73, doi:10.1002/jgt.3190040107, MR558453. But then e.g. a cycle in the bipartite graph turns into a cycle with alternating edge orientations in the directed graph, not exactly what you probably want.

$\endgroup$
2
  • 1
    $\begingroup$ This seems to be related to the Kronecker cover (canonical double cover) of undirected graphs. $\endgroup$ Mar 8, 2010 at 9:57
  • 1
    $\begingroup$ I guess the Kronecker cover is what you get if you make an undirected graph directed (by turning each undirected edge into two directed edges) and then looking at the equivalent bipartite graph. But of course the directed-bipartite equivalence works even when the directed graph has edges only in one direction between some pairs of vertices. $\endgroup$ Mar 14, 2010 at 5:26
4
$\begingroup$

Some classical theorems involving complete graphs have analogues involving complete bipartite graphs. For example, the complete graph $K_n$ has $n^{n-2}$ spanning trees, while the complete bipartite graph $K_{m,n}$ has $n^{m-1} m^{n-1}$ spanning trees. Finding the largest complete subgraph of a graph is a standard NP-hard problem, and finding the largest (in terms of number of edges) complete bipartite subgraph of a bipartite graph is also an NP-hard problem.

But possibly the area of graph theory that has most benefited from the analogy between general graphs and bipartite graphs is matching theory. Matching theory tends to be easier in the bipartite case, but the bipartite case often gives us clues for the non-bipartite case. For example, finding a maximum matching in a bipartite graph is solvable in polynomial time, but nontrivially so, and this leads us to look for a polytime algorithm for maximum matching in a non-bipartite graph (which does exist, but is more complicated than in the bipartite case). Lovász and Plummer's Matching Theory, now back in print thanks to the American Mathematical Society, gives an excellent account of the interplay between bipartite and non-bipartite matching.

$\endgroup$
2
$\begingroup$

The Degree-Diameter Problem vs. the Degree-Diameter Problem For Bipartite Graphs. Given natural numbers d and k, find the largest possible number Nb(d,k) of vertices in a bipartite graph of maximum degree d and diameter k.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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