ALCOMFT-TR-02-81

Bolette Ammitzbøll Madsen, Jesper Makholm Nielsen and Bjarke Skjernaa
On the Number of Maximal Bipartite Subgraphs of a Graph
Århus. Work package 4. May 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ⁿ such subgraphs, which improves an earlier lower bound by Schiermeyer (1996). We show an upper bound of n· 12^n/4 \approx n· 1.8613ⁿ 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\dash colourability of a graph running within the same time bound.

Postscript file: ALCOMFT-TR-02-81.ps.gz (140 kb).