On the number of maximal bipartite subgraphs of a graph |
| |
Authors: | Jesper Makholm Byskov Bolette Ammitzbll Madsen Bjarke Skjernaa |
| |
Institution: | Jesper Makholm Byskov,Bolette Ammitzbøll Madsen,Bjarke Skjernaa |
| |
Abstract: | We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105n/10 ≈ 1.5926n; such subgraphs show an upper bound of O(12n/4) = O(1.8613n) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005 |
| |
Keywords: | maximal bipartite subgraphs coloring coloring algorithms |
|