Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 11 down vote accepted

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.

share|improve this answer
    
Thanks, David! That was useful. –  Tomaž Pisanski Mar 7 '10 at 5:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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