Geodesic
Graph Orientations and Linear Extensions.
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014).

Voir la notice de l'article provenant de la source Episciences

Given an underlying undirected simple graph, we consider the set of all acyclic orientations of its edges. Each of these orientations induces a partial order on the vertices of our graph, and therefore we can count the number of linear extensions of these posets. We want to know which choice of orientation maximizes the number of linear extensions of the corresponding poset, and this problem is solved essentially for comparability graphs and odd cycles, presenting several proofs. We then provide an inequality for general graphs and discuss further techniques. 
@article{DMTCS_2014_special_265_a80,
     author = {Iriarte, Benjamin},
     title = {Graph {Orientations} and {Linear} {Extensions.}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)},
     year = {2014},
     doi = {10.46298/dmtcs.2455},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2455/}
}
TY  - JOUR
AU  - Iriarte, Benjamin
TI  - Graph Orientations and Linear Extensions.
JO  - Discrete mathematics & theoretical computer science
PY  - 2014
VL  - DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2455/
DO  - 10.46298/dmtcs.2455
LA  - en
ID  - DMTCS_2014_special_265_a80
ER  - 
%0 Journal Article
%A Iriarte, Benjamin
%T Graph Orientations and Linear Extensions.
%J Discrete mathematics & theoretical computer science
%D 2014
%V DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2455/
%R 10.46298/dmtcs.2455
%G en
%F DMTCS_2014_special_265_a80
Iriarte, Benjamin. Graph Orientations and Linear Extensions.. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014). doi : 10.46298/dmtcs.2455. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2455/

Cité par Sources :