Two tree-width-like graph invariants

H. Holst, van der

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)
    1 Downloads (Pure)


    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.
    Original languageEnglish
    Pages (from-to)633-651
    Issue number4
    Publication statusPublished - 2003


    Dive into the research topics of 'Two tree-width-like graph invariants'. Together they form a unique fingerprint.

    Cite this