On the Block Number of Graphs

A k-block in a graph G is a maximal set of at least k vertices no two of which can be separated in G by deleting fewer than k vertices. The block number β(G) of G is the maximum integer k for which G contains a k-block. We prove a structure theorem for graphs without a $(k+1)$-block, showing that every such graph has a tree-decomposition in which every torso has at most k vertices of degree 2k² or greater. This yields a qualitative duality, since every graph that admits such a decomposition has block number at most 2k². We also study k-blocks in graphs from classes of graphs G that exclude some fixed graph as a topological minor and prove that every G ∈ G satisfies β(G) ≤ c√[3]|G| for some constant c = c( G). Moreover, we show that every graph of tree-width at least 2k² has a minor containing a k-block. This bound is best possible up to a multiplicative constant.