On a bipartition problem of Bollobás and Scott

Authors: Baogang Xu Xingxing Yu

Publish Date: 2010/08/24

Volume: 29, Issue: 5, Pages: 595-618

PDF Link

Abstract

The bipartite density of a graph G is max EH/EG H is a bipartite subgraph of G It is NPhard to determine the bipartite density of any trianglefree cubic graph A biased maximum bipartite subgraph of a graph G is a bipartite subgraph of G with the maximum number of edges such that one of its partite sets is independent in G Let mathcalH denote the collection of all connected cubic graphs which have bipartite density tfrac4 5 and contain biased maximum bipartite subgraphs Bollobás and Scott asked which cubic graphs belong to mathcalH This same problem was also proposed by Malle in 1982 We show that any graph in mathcalH can be reduced through a sequence of three types of operations to a member of a well characterized class As a consequence we give an algorithm that decides whether a given graph G belongs to mathcalH Our algorithm runs in polynomial time provided that G has a constant number of triangles that are not blocks of G and do not share edges with any other triangles in G

Keywords: