pith. sign in

arxiv: 2606.07748 · v1 · pith:4JCFJF5Qnew · submitted 2026-06-05 · 🧮 math.CO · cs.DM

Decomposing tournaments into comparability graphs

Pierre Aboulker , Logan Crew , Julien Duron , Xinyue Fan , Hugo Jacob , R\'emy Kimbrough , Hidde Koerts , Benjamin Moore
show 2 more authors
Sophie Spirkl St\'ephan Thomass\'e
This is my paper

Pith reviewed 2026-06-27 21:25 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords partial order decomposition numberdichromatic numberdirected clique numbertournamentssubstitutiondic-bounded classesposet tournaments
0
0 comments X

The pith

Every digraph D satisfies dic(D) ≤ diomega(D)^pod(D), where pod(D) is the minimum number of partial orders covering its arcs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines pod(D) as the smallest integer k such that the arcs of D can be partitioned into the arcs of k partial orders. It proves the inequality dic(D) ≤ diomega(D)^pod(D) for every digraph D. This immediately shows that any class of digraphs with bounded pod is polynomially dic-bounded. The same bound is used to prove that the substitution closure of any tournament class with bounded dichromatic number remains polynomially dic-bounded, and to obtain further results on poset tournaments and domination number.

Core claim

The paper proves that dic(D) ≤ diomega(D)^pod(D) for every digraph D, with pod(D) the smallest k such that A(D) equals the union of A(P_i) for k partial orders P_i on the same vertex set. As a direct consequence, every class with bounded pod is polynomially dic-bounded. The same inequality yields that the substitution closure of any class of tournaments with bounded dichromatic number is polynomially dic-bounded.

What carries the argument

The partial order decomposition number pod(D), the smallest k such that the arc set of D is covered by the arc sets of k partial orders; it supplies the exponent in the bound because each partial order's transitive acyclic structure controls how many additional colors are needed when the covers are combined.

If this is right

  • Every class of digraphs with bounded pod is polynomially dic-bounded.
  • The substitution closure of any class of tournaments with bounded dichromatic number is polynomially dic-bounded.
  • Poset tournaments of bounded dimension are dic-bounded.
  • Certain explicit families of tournaments admit polynomial lower bounds on their directed clique number.
  • Tournaments with bounded pod have bounded domination number.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • pod(D) may serve as an intermediate parameter for proving dic-boundedness in other substitution-closed families of digraphs.
  • The decomposition technique could be adapted to obtain polynomial bounds for additional directed graph parameters such as directed chromatic number variants.
  • If pod(D) can be computed or approximated in polynomial time for restricted classes, it would yield explicit coloring algorithms for those classes.

Load-bearing premise

The bound on dichromatic number is obtained by an inductive coloring argument that uses the transitivity and acyclicity inside each partial order to limit the growth of monochromatic directed cycles across the union.

What would settle it

A single digraph D in which the dichromatic number exceeds the directed clique number raised to the power of its partial order decomposition number.

read the original abstract

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 $\dic$-bounded, thereby making progress on a question of Aubian, Charbit, Lopes, and the first author. As further applications of $pod$, we prove that poset tournaments of bounded dimension are $\dic$-bounded, derive polynomial lower bounds on the directed clique number of an explicit family of tournaments, thereby answering a conjecture of Gutowski and Rams, and show that tournaments with bounded $pod$ have bounded domination number.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces the partial order decomposition number pod(D) of a digraph D as the smallest integer k such that the arc set A(D) is the union of the arc sets of k partial orders on V(D). It proves the inequality dic(D) ≤ diomega(D)^pod(D) for every digraph D. As consequences, every class with bounded pod is polynomially dic-bounded; the substitution closure of any class of tournaments with bounded dichromatic number is polynomially dic-bounded; poset tournaments of bounded dimension are dic-bounded; an explicit family of tournaments yields polynomial lower bounds on the directed clique number (answering a conjecture of Gutowski and Rams); and tournaments with bounded pod have bounded domination number.

Significance. If the central inequality holds, the new parameter pod supplies a uniform way to obtain polynomial dic-bounds from arc covers by partial orders, directly addressing questions on substitution-closed tournament classes and providing explicit constructions that resolve a stated conjecture. The applications demonstrate concrete utility beyond the abstract bound.

minor comments (2)
  1. [Title and Abstract] Title/Abstract: the title emphasizes decomposition of tournaments into comparability graphs, yet the body works with arc covers by partial orders on general digraphs; an explicit sentence linking the two notions (via the comparability graph of the transitive closure) would clarify the scope for readers.
  2. [Section 2 (proof of main theorem)] The manuscript is described as a short note; if the proof of the main inequality occupies only a few lines, a brief outline of the inductive coloring argument (assigning pod(D)-tuples of colors from a diomega(D)-set, using transitivity to preserve acyclicity) would improve readability without lengthening the paper.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation to accept the manuscript. We are pleased that the introduction of pod(D) and the central inequality were viewed as providing a useful uniform approach to polynomial dic-bounds, along with the listed applications.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central result states that dic(D) ≤ diomega(D)^pod(D) where pod(D) is defined as the minimum number of partial orders whose arcs cover A(D). This inequality is presented as a theorem to be proved from the definition of pod(D) together with standard properties of partial orders and the meanings of dic and diomega; the abstract and reader's summary give no indication that the bound is obtained by renaming, fitting, or reducing to a self-citation. No load-bearing step is shown to be equivalent to its own input by construction, and the derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the newly defined pod(D) together with standard facts about partial orders and dichromatic number; no numerical free parameters are introduced.

axioms (2)
  • standard math A partial order is a transitive acyclic binary relation; its arcs form a transitive tournament.
    Invoked implicitly when the paper decomposes arcs into partial orders to control cycles.
  • standard math Dichromatic number and directed clique number are well-defined for every digraph.
    Background definitions used throughout the statements.
invented entities (1)
  • partial order decomposition number pod(D) no independent evidence
    purpose: Minimum number of partial orders whose arc sets union to A(D)
    Newly defined parameter whose value controls the exponential bound; no external falsifiable prediction supplied in the abstract.

pith-pipeline@v0.9.1-grok · 5779 in / 1481 out tokens · 24990 ms · 2026-06-27T21:25:38.889056+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

  1. [1]

    Clique number of tournaments.arXiv preprint, arXiv:2310.04265, 2023

    Pierre Aboulker, Guillaume Aubian, Pierre Charbit, and Raul Lopes. Clique number of tournaments.arXiv preprint, arXiv:2310.04265, 2023

    Pith/arXiv arXiv 2023

  2. [2]

    Computing the degreewidth of a digraph is hard.Discrete Mathematics & Theoretical Computer Science, 28(Graph Theory), 2026

    Pierre Aboulker, Nacim Oijid, Robin Petit, Mathis Rocton, and Christopher-Lloyd Simon. Computing the degreewidth of a digraph is hard.Discrete Mathematics & Theoretical Computer Science, 28(Graph Theory), 2026

    2026

  3. [3]

    Ramsey-type theorems with forbidden subgraphs.Combinatorica, 21(2):155–170, 2001

    Noga Alon, J´ anos Pach, and J´ ozsef Solymosi. Ramsey-type theorems with forbidden subgraphs.Combinatorica, 21(2):155–170, 2001

    2001

  4. [4]

    Les probl` emes de coloration en th´ eorie des graphes

    Claude Berge. Les probl` emes de coloration en th´ eorie des graphes. InAnnales de l’ISUP, volume 9, pages 123–160, 1960

    1960

  5. [5]

    A proof of the erd˝ os–sands–sauer–woodrow con- jecture.Journal of Combinatorial Theory, Series B, 137:316–319, 2019

    Nicolas Bousquet, William Lochet, and St´ ephan Thomass´ e. A proof of the erd˝ os–sands–sauer–woodrow con- jecture.Journal of Combinatorial Theory, Series B, 137:316–319, 2019

    2019

  6. [6]

    Separating polynomialχ-boundedness fromχ- boundedness.Combinatorica, 44(1):1–8, 2024

    Marcin Bria´ nski, James Davies, and Bartosz Walczak. Separating polynomialχ-boundedness fromχ- boundedness.Combinatorica, 44(1):1–8, 2024

    2024

  7. [7]

    Domination in tournaments.Journal of Combinatorial Theory, Series B, 130:98–113, 2018

    Maria Chudnovsky, Ringi Kim, Chun-Hung Liu, Paul Seymour, and St´ ephan Thomass´ e. Domination in tournaments.Journal of Combinatorial Theory, Series B, 130:98–113, 2018

    2018

  8. [8]

    Substitution andχ-boundedness.Journal of Combinatorial Theory, Series B, 103(5):567–586, 2013

    Maria Chudnovsky, Irena Penev, Alex Scott, and Nicolas Trotignon. Substitution andχ-boundedness.Journal of Combinatorial Theory, Series B, 103(5):567–586, 2013

    2013

  9. [9]

    On chromatic number of infinite graph.Theory of Graphs (Proc

    Paul Erd˝ os and Andr´ as Hajnal. On chromatic number of infinite graph.Theory of Graphs (Proc. Coll. Tihany 1966, P. Erd˝ os and G. Katona, eds.), pages 61–99, 1966

    1966

  10. [10]

    A note on the complexity of directed clique, 2026

    Grzegorz Gutowski and Miko laj Rams. A note on the complexity of directed clique, 2026

    2026

  11. [11]

    Partitioning perfect graphs into comparability graphs.arXiv preprint, arXiv:2408.13523, 2024

    Andr´ as Gy´ arf´ as, M´ arton Marits, and G´ eza T´ oth. Partitioning perfect graphs into comparability graphs.arXiv preprint, arXiv:2408.13523, 2024

    arXiv 2024

  12. [12]

    Harner and Roger C

    Charles C. Harner and Roger C. Entringer. Arc colorings of digraphs.Journal of Combinatorial Theory, Series B, 13(3):219–225, 1972. 9

    1972

  13. [13]

    Acyclic subgraphs with high chromatic number.European Journal of Combinatorics, 75:11–18, 2019

    Safwat Nassar and Raphael Yuster. Acyclic subgraphs with high chromatic number.European Journal of Combinatorics, 75:11–18, 2019

    2019

  14. [14]

    The dichromatic number of a digraph.Journal of Combinatorial Theory, Series B, 33(3):265–270, 1982

    Victor Neumann-Lara. The dichromatic number of a digraph.Journal of Combinatorial Theory, Series B, 33(3):265–270, 1982

    1982

  15. [15]

    Some results and problems on tournament structure.Journal of Combinatorial Theory, Series B, 173:146–183, 2025

    Tung Nguyen, Alex Scott, and Paul Seymour. Some results and problems on tournament structure.Journal of Combinatorial Theory, Series B, 173:146–183, 2025

    2025

  16. [16]

    A survey ofχ-boundedness.Journal of Graph Theory, 95(3):473–504, 2020

    Alex Scott and Paul Seymour. A survey ofχ-boundedness.Journal of Graph Theory, 95(3):473–504, 2020. 10

    2020