6
$\begingroup$

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?

$\endgroup$

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
0

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.