Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Graph Orientations and Linear Extensions.

Abstract : 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.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01207561
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, October 1, 2015 - 9:28:27 AM
Last modification on : Wednesday, June 26, 2019 - 2:48:03 PM
Long-term archiving on: : Saturday, January 2, 2016 - 10:47:44 AM

File

dmAT0181.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Benjamin Iriarte. Graph Orientations and Linear Extensions.. 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), 2014, Chicago, United States. pp.945-956, ⟨10.46298/dmtcs.2455⟩. ⟨hal-01207561⟩

Share

Metrics

Record views

52

Files downloads

571