The number of linear extensions of bipartite graphs
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.
- A combinatorial bijection between linear extensions of equivalent orders
- Regular subgraphs of linear extension graphs.
- scientific article; zbMATH DE number 1292171 (Why is no real title available?)
- Graph orientations and linear extensions
- scientific article; zbMATH DE number 952616 (Why is no real title available?)
- Linear extensions of diamond posets
- A relation between the comparability graph and the number of linear extensions
This page was built for publication: The number of linear extensions of bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114718)
