Tuesday, 15 February 2011

co.combinatorics - Finding a cycle of fixed length in a bipartite graph

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?

No comments:

Post a Comment