|
6
1
|
Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of fixed length Edit: There is natural refinement of this question: what happens if the graph has boundend valence, e.g. if the bipartite graph is cubic? |
|||
|
|
|
10
|
Finding a cycle of length 2k in an arbitrary graph is the same thing as finding a cycle of length 4k in the bipartite graph formed by subdividing every edge. So in general even cycles of fixed length are no easier to find in bipartite graphs than in arbitrary graphs. But it's possible that the lengths that are 2 mod 4 are easier to find than the lengths that are 0 mod 4, in bipartite graphs. |
|||
|
