If we take a graph $G$, and sequentially delete the edge which belongs to the most odd cycles until we have a bipartite graph, will at least half the edges remain when the graph is bipartite?
Background: It is well known every graph, $G$, has a bipartite subgraph with at least $e(G)/2$ edges ($e(G)$ is the number of edges in $G$). One way to find such a subgraph is to greedily add vertices to one of two glasses at each step minimizing the number of crossing edges. So my interest is in a greedy method based on the cycle interpretation bipartiteness rather than the two color interpretation.
Note: This problem has bean crossposted and solved in the negative on MO https://mathoverflow.net/questions/180370/a-method-for-making-a-graph-bipartite Interestingly, we can not even replace $1/2$ with any positive constant.
This problem is generally referred to in the literature as the Zarankiewicz Problem which has a very informative wiki page at http://en.wikipedia.org/wiki/Zarankiewicz_problem.
This concentrates mainly on the graph-theoretic bounds on the minimal number of edges which must be removed from a graph to render it bipartite. One key insight is offered by considering the maximal clique structure of the graph. If the largest complete subgraph (or clique) has m nodes,say m even, it is not possible to obtain a two-coloring of the m nodes without removing at least m/2*(m/2-1) edges. This suggest one possible route for an algorithm would be a branch and bound method based on an analysis of the clique structure. Tighter bounds can be obtained as pointed out in the wiki website referred to above, based on the graph structure given a knowledge of the maximal clique number.
Heuristic methods, based on cycle structure, may also be of interest in practical applications of this problem, of course.