Local bipartite Turan graph partitioning

Motivated by the NP-Hard problem of finding a minimum-weight balanced bipartition of an edge-weighted complete graph, we study the class of graphs having the same degrees as bipartite 'fur.an graphs. In particular, we establish a maximal set of linear equations satisfied by the counts of the possible incidences of 3- and 4-cycles on such graphs. This leads to extremal results which we exploit in a heuristic for the partitioning problem. Preliminary computational results appear to be quite promising. Further results are established linking various adjacency concepts and measures of non-bipartiteness for such graphs. We also discuss a Lagrangian bound for the partitioning problem and demonstrate its potential power via a family of examples.