Hypertree-depth and minors in hypergraphs

We introduce two new notions for hypergraphs, hypertree-depth and minors in hypergraphs. We characterise hypergraphs of bounded hypertree-depth by the ultramonotone robber and marshals game, by vertex-hyperrankings and by centred hypercolourings. Furthermore, we show that minors in hypergraphs are 'well-behaved' with respect to hypertree-depth and other hypergraph invariants, such as generalised hypertree-depth and generalised hyperpath-width. We work in the framework of hypergraph pairs (G, H), consisting of a graph G and a hypergraph H that share the same vertex set. This general framework allows us to obtain hypergraph minors, graph minors and induced graph minors as special cases. (C) 2012 Elsevier B.V. All rights reserved.