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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .