On the Number of Maximal Bipartite Subgraphs of a Graph

  • Bolette Ammitzbøll Madsen
  • Jesper Makholm Byskov
  • Bjarke Skjernaa

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} ~= 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.
Published
2002-04-05
How to Cite
Madsen, B., Byskov, J., & Skjernaa, B. (2002). On the Number of Maximal Bipartite Subgraphs of a Graph. BRICS Report Series, 9(17). https://doi.org/10.7146/brics.v9i17.21735