A Note on Contraction Degeneracy
Thomas Wolle, Arie M. C. A. Koster, Hans L. Bodlaender · 2004
Abstract. The parameter contraction degeneracy | the maximum min-imum degree over all minors of a graph | is a treewidth lower bound and was rst dened in [3]. In experiments it was shown that this lower bound improves upon other treewidth lower bounds [3]. In this note, we examine some relationships between the contraction degeneracy and con-nected components of a graph, blocks of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described. 1