Return to Question

spelling

view source

edited Mar 7 2010 at 15:55

Is there a bipartite analogue analog of graph theory?

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:

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.
Minimal Girth. For graphs, 3 is the minimal possible length of a cycle. For bipartite graphs, the analogous number is 4.*
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.

[made Community Wiki]

view source

asked Mar 7 2010 at 15:36

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:

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.
Minimal Girth. For graphs, 3 is the minimal possible length of a cycle. For bipartite graphs, the analogous number is 4. *
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.