Two Tree-Width-Like GraphInvariants

In this paper we introduce two tree-width-like graphinvariants. The first graph invariant, which we denote by⁼(G), is defined in terms of positivesemi-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 graphinvariant, which we denote by (G), is defined in terms of a certainconnected 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 theseinvariants under certain transformations. We show that⁼(G)=(G)for any graph G with⁼(G)4, and we give minimal forbiddenminor characterizations for the graphs satisfying⁼(G)kfor k=1,2,3,4.This paper is extracted from two chapters of [7].This work was done while the author was at the Centrum voorWiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, TheNetherlands.