On the Number of Maximal Bipartite Subgraphs of a Graph - Madsen, Bolette Ammitzbøll; Byskov, Jesper Makholm; Skjernaa, Bjarke (BRICS Report Series, 2002)
We show new lower and upper bounds on the number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105^n/10 = 1.5926^n such subgraphs, which improves an earlier lower bound by Schiermeyer (1996). We show an upper bound of n . 12^n/4 = n . 1.8613^n and give an algorithm that lists all maximal induced bipartite subgraphs in time proportional to this bound. This is used in an algorithm for checking 4-colourability of a graph running within the same time bound.