Tree-decompositions, tree-representability and chordal graphs (Q1104938)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Tree-decompositions, tree-representability and chordal graphs
scientific article

    Statements

    Tree-decompositions, tree-representability and chordal graphs (English)
    0 references
    0 references
    1988
    0 references
    The following assertions are shown to be equivalent, for any countable graph G: (1) G can be represented as the intersection graph of a family of subtrees of a tree; (2) G admits a tree-decomposition (Robertson/Seymour) into primes; (3) G is chordal, and G admits a simplicial tree-decomposition (Halin) into primes; (4) G is chordal, and neither of two specified graphs is contained in G as a simplicial minor.
    0 references
    intersection graph
    0 references
    tree-decomposition
    0 references
    chordal
    0 references
    simplicial minor
    0 references

    Identifiers