排序方式: 共有1条查询结果,搜索用时 0 毫秒
1
1.
Jesper Makholm Byskov Bolette Ammitzbll Madsen Bjarke Skjernaa 《Journal of Graph Theory》2005,48(2):127-132
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 相似文献
1