Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 37 min ago
PreprintCC0arXiv

Chains and unique transitive orientations of prime graphs

  • Robert Brignall
  • Sean Mandrick
  • Vincent Vatter
Open at sourcePDFDOICite

Abstract

We give a short, conceptual proof that prime graphs have at most two transitive orientations, a much-quoted result of Gallai. Our proof uses chains, introduced by Chudnovsky, Kim, Oum, and Seymour, which provide a transparent characterization of primality. Transitivity induces a forcing relation on edges; using chains, we show that any two edges of a prime graph are equivalent under this relation, and thus any transitive orientation is unique up to reversal.

Related

  1. Orientations without transitive arcs for cubic graphs and phylogenetic networks
    Janosch Döcker, Simone Linz
    arXivPreprintarXiv licenceFull textEvolutionary biologyCombinatorics & discrete mathematicsarXiv
  2. An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
    Thomas Dueholm Hansen, Uri Zwick
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Multi-Way Expansion, Laplacian Gaps, and Imprimitivity in Vertex-Transitive Graphs
    Zejun Huang, Chenxi Yang
    HALPreprintLicence Ouverte 2.0Full textGeneral mathematicsHAL
  4. Vertex-transitive strongly regular graphs in the switching class of doubly transitive two-graphs
    Robert F. Bailey, Gábor P. Nagy, Valentino Smaldore
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Modulo k-orientations of highly edge-connected signed graphs
    You Lu, Zhengke Miao, Zhenyu Tian +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{brignall2026chains,
  title = {{Chains and unique transitive orientations of prime graphs}},
  author = {Robert Brignall and Sean Mandrick and Vincent Vatter},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08057},
  eprint = {2609.08057},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08057},
  note = {CC0},
}
RIS
TY  - UNPB
TI  - Chains and unique transitive orientations of prime graphs
AU  - Robert Brignall
AU  - Sean Mandrick
AU  - Vincent Vatter
PY  - 2026
DA  - 2026/09/07
PB  - arXiv
DO  - 10.48550/arxiv.2609.08057
UR  - https://arxiv.org/abs/2609.08057
AB  - We give a short, conceptual proof that prime graphs have at most two transitive orientations, a much-quoted result of Gallai. Our proof uses chains, introduced by Chudnovsky, Kim, Oum, and Seymour, which provide a transparent characterization of primality. Transitivity induces a forcing relation on edges; using chains, we show that any two edges of a prime graph are equivalent under this relation, and thus any transitive orientation is unique up to reversal.
ER  -