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
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