On the "largeur d'arborescence''

H. Holst, van der

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    Let la(G) be the invariant introduced by Colin de Verdière [J. Comb. Theory, Ser. B., 74:121-146, 1998], which is defined as the smallest integer n0 such that G is isomorphic to a minor of Kn×T, where Kn is a complete graph on n vertices and where T is an arbitrary tree. In this paper, we give an alternative definition of la(G), which is more in terms of the tree-width of a graph. We give the collection of minimal forbidden minors for the class of graphs G with la(G)k, for k=2, 3. We show how this work on la(G) can be used to get a forbidden minor characterization of the graphs with (G)3. Here, (G) is another graph parameter introduced in the above cited paper.
    Original languageEnglish
    Pages (from-to)24-52
    JournalJournal of Graph Theory
    Volume41
    Issue number1
    DOIs
    Publication statusPublished - 2002

    Fingerprint

    Forbidden Minor
    Graph in graph theory
    Treewidth
    Complete Graph
    Minor
    Isomorphic
    Integer
    Invariant
    Alternatives
    Arbitrary

    Cite this

    Holst, van der, H. / On the "largeur d'arborescence''. In: Journal of Graph Theory. 2002 ; Vol. 41, No. 1. pp. 24-52.
    @article{2a5c2dfbd6194889bc5a14f65ba4f9ae,
    title = "On the {"}largeur d'arborescence''",
    abstract = "Let la(G) be the invariant introduced by Colin de Verdi{\`e}re [J. Comb. Theory, Ser. B., 74:121-146, 1998], which is defined as the smallest integer n0 such that G is isomorphic to a minor of Kn×T, where Kn is a complete graph on n vertices and where T is an arbitrary tree. In this paper, we give an alternative definition of la(G), which is more in terms of the tree-width of a graph. We give the collection of minimal forbidden minors for the class of graphs G with la(G)k, for k=2, 3. We show how this work on la(G) can be used to get a forbidden minor characterization of the graphs with (G)3. Here, (G) is another graph parameter introduced in the above cited paper.",
    author = "{Holst, van der}, H.",
    year = "2002",
    doi = "10.1002/jgt.10046",
    language = "English",
    volume = "41",
    pages = "24--52",
    journal = "Journal of Graph Theory",
    issn = "0364-9024",
    publisher = "Wiley-Liss Inc.",
    number = "1",

    }

    On the "largeur d'arborescence''. / Holst, van der, H.

    In: Journal of Graph Theory, Vol. 41, No. 1, 2002, p. 24-52.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - On the "largeur d'arborescence''

    AU - Holst, van der, H.

    PY - 2002

    Y1 - 2002

    N2 - Let la(G) be the invariant introduced by Colin de Verdière [J. Comb. Theory, Ser. B., 74:121-146, 1998], which is defined as the smallest integer n0 such that G is isomorphic to a minor of Kn×T, where Kn is a complete graph on n vertices and where T is an arbitrary tree. In this paper, we give an alternative definition of la(G), which is more in terms of the tree-width of a graph. We give the collection of minimal forbidden minors for the class of graphs G with la(G)k, for k=2, 3. We show how this work on la(G) can be used to get a forbidden minor characterization of the graphs with (G)3. Here, (G) is another graph parameter introduced in the above cited paper.

    AB - Let la(G) be the invariant introduced by Colin de Verdière [J. Comb. Theory, Ser. B., 74:121-146, 1998], which is defined as the smallest integer n0 such that G is isomorphic to a minor of Kn×T, where Kn is a complete graph on n vertices and where T is an arbitrary tree. In this paper, we give an alternative definition of la(G), which is more in terms of the tree-width of a graph. We give the collection of minimal forbidden minors for the class of graphs G with la(G)k, for k=2, 3. We show how this work on la(G) can be used to get a forbidden minor characterization of the graphs with (G)3. Here, (G) is another graph parameter introduced in the above cited paper.

    U2 - 10.1002/jgt.10046

    DO - 10.1002/jgt.10046

    M3 - Article

    VL - 41

    SP - 24

    EP - 52

    JO - Journal of Graph Theory

    JF - Journal of Graph Theory

    SN - 0364-9024

    IS - 1

    ER -