The number of linear extensions of bipartite graphs (Q1114718)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The number of linear extensions of bipartite graphs
scientific article

    Statements

    The number of linear extensions of bipartite graphs (English)
    0 references
    0 references
    1988
    0 references
    A linear extension of a partially ordered set P is a total order L of elements of P such that \(x\leq y\) in P implies \(x\leq y\) in L. An acyclic directed graph G can be considered as a partial order on its vertex set; we have \(x\leq y\) in this order if and only if a directed path in G goes from x to y. A natural orientation of a bipartite graph with the bipartition classes \(V_ 1\), \(V_ 2\) is the orientation such that one of the sets \(V_ 1\), \(V_ 2\) is the set of initial vertices of all edges and the other is the set of all terminal ones. It is proved that any acyclic orientation of a bipartite graph G has a smaller number of linear extensions than a natural one. This was a conjecture of M. D. Atkinson.
    0 references
    acyclic directed graph
    0 references
    natural orientation
    0 references
    bipartite graph
    0 references
    acyclic orientation
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references