On the Number of Maximal Bipartite Subgraphs of a Graph

Bolette Ammitzbøll Madsen
Jesper Makholm Nielsen
Bjarke Skjernaa

April 2002

Abstract:

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} \approx 1.5926^n$ such subgraphs, which improves an earlier lower bound by Schiermeyer (1996). We show an upper bound of $n\cdot 12^{n/4} \approx n\cdot 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

Available as PostScript, PDF.

Last modified: 2003-06-08 by webmaster.