Two tree-width-like graph invariants

In this paper we introduce two tree-width-like graph invariants. The first graph invariant, which we denote by =(G), is defined in terms of positive semi-definite matrices and is similar to the graph invariant (G), introduced by Colin de Verdière in [J. Comb. Theory, Ser. B., 74:121–146, 1998]. The second graph invariant, which we denote by (G), is defined in terms of a certain connected subgraph property and is similar to (G), introduced by van der Holst, Laurent, and Schrijver in [J. Comb. Theory, Ser. B., 65:291–304, 1995]. We give some theorems on the behaviour of these invariants under certain transformations. We show that =(G)=(G) for any graph G with =(G)4, and we give minimal forbidden minor characterizations for the graphs satisfying =(G)k for k=1,2,3,4.