The (largest) bipartite subgraph I'm looking for any idea or algorithm that solves the problem of finding bipartite subgraphs in any graph. In general, I'd like to divide graph into the smallest number of bipartite subgraphs. My first thought was to find the largest bipartite subgraph and repeat it until they set of the remaining vertices is empty, but I don't know how to solve this problem in polynomial (or pseudo-polynomial) time.
 A: I assume here that you're looking for induced subgraphs, and I address your "general" problem. It's NP-complete.
A bipartite graph is a 2-colorable graph ; so an induced subgraph that is bipartite is an incomplete (not going through all the vertices) 2-coloration of the graph.
Looking for the smallest decomposition in bipartite graphs, it means looking for a complete coloration of the graph with $2k$ colors, where $k$ is your number of bipartite graphs. Say you have decomposition in $k$ bipartite graphs, then you can easily deduce a $2k$ coloration of your graph, and conversely when you have a $2k$ coloration you can group your colors two by two, and the induced subgraphs will be bipartite.
But deciding whether a graph is $2k$-colorable is NP-complete. So either your subproblem itself is NP-complete, or it is unoptimal for your global problem. Probably both.
Concerning your "local" subproblem, it can be reformulated as finding the biggest set of two colors in the graph. I'd guess that it must be NP-hard ; finding the biggest set of one color (which is the largest anticlique, or independent set) is already strongly NP-hard.
