Decomposing tournaments into comparability graphs

Pierre Aboulker, Logan Crew, Julien Duron, Xinyue Fan, Hugo Jacob, Rémy Kimbrough, Hidde Koerts, Benjamin Moore, Sophie Spirkl, Stéphan Thomassé

arXivarxiv/2606.07748Jun 5, 2026math.COscore 0

In this note, we introduce the \emph{partial order decomposition number} of a digraph $D$, denoted $pod(D)$, defined as the minimum integer $k$ such that $A(D)=A(P_1)\cup\cdots\cup A(P_k)$, where $P_1,\ldots,P_k$ are partial orders on $V(D)$. We prove that $\dic(D)\le \diomega(D)^{pod(D)}$ for every digraph $D$. In particular, every class of digraphs with bounded $pod$ is polynomially $\dic$-bounded. We apply this to tournaments, showing that if $\mathcal C$ is a class of tournaments with bounded dichromatic number, then the closure of $\mathcal C$ under substitution is polynomially…

SourceJSON

Comments and reviews

No comments yet.

API

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