Open Research Index

Chains and unique transitive orientations of prime graphs

Robert Brignall, Sean Mandrick, Vincent Vatter

arXivarxiv/2609.08057Sep 7, 2026math.COscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2609.08057
curl -X POST /api/v1/records/arxiv/2609.08057/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.08057/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'