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 Dive into the research topics of 'On the "largeur d'arborescence'''. Together they form a unique fingerprint.

    Cite this