M
<P><CENTER>
<H2>
Parallel Generation of Large Bipartite Subgraphs in Cubic Graphs
</H2>
</CENTER>

We consider the problem of finding in parallel a Maximum Bipartite 
Subgraph of a cubic graph G(V,E), that is known to be NP-complete 
even if the graph is triangle-free.  We approach the problem as a Max 
Cut one.  We analyze the solution structure according to the degree of 
vertices in the bipartition and to the odd girth g of the graph, 
showing that the number of edges in the bipartite subgraph is at least 
{{9g-3} / {8g}}|V|.  The result of a wide experimentation rounds 
off the paper.