On a bipartition problem of Bollobás and Scott (Q624186)

The bipartite density of a graph \(G\) is \(\max\{| E(H)| /| E(G)|\, :\,H\) is a bipartite subgraph of \(G\}\). Let \(\mathcal H\) denote the collection of all connected cubic graphs which have bipartite density \(\frac 45\) and contain a maximum bipartite subgraph such that one of its partite sets is independent in \(G\). In the paper, it is proved that any graph in \(\mathcal H\) can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence, an algorithm which decides whether a given graph belongs to \(\mathcal H\) is given.