χ-boundedness of matchings in ordered graphs

Conjecture 4.11 · arXiv:2310.04265

arXiv Conjecture high confidence— first stated 2023-10-06

Authors: Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes

Status open medium confidence

Conjecture 4.11 of arXiv:2310.04265 asserts that for any ordered graph $(M,\prec)$ with maximum degree $1$, the class of $(M,\prec)$-free ordered graphs is $\chi$-bounded; this would imply $\overrightarrow{\chi}$-boundedness results for certain tournament classes via the paper's backedge-graph correspondence. No paper resolving this conjecture was found. Two papers citing the source were identified via Semantic Scholar — arXiv:2602.09863 (Crew et al., 2026) on characterising large clique number in tournaments, and arXiv:2407.19270 (Aboulker et al., 2024) on degreewidth of digraphs — but neither could be verified as addressing the ordered-graph chi-boundedness conjecture within the web-call budget.

Reviewer notes. Two papers citing arXiv:2310.04265 were located via the Semantic Scholar API: arXiv:2602.09863 (Crew, Fan, Koerts, Moore, Spirkl 2026, 'Characterizing Large Clique Number in Tournaments') and arXiv:2407.19270 (Aboulker, Oijid, Petit, Rocton, Simon 2024, 'Computing the degreewidth of a digraph is hard'). Their full texts were not fetched (5-call cap reached), so it is unknown whether either addresses Conjecture 4.11. The conjecture is a supporting technical statement linking ordered-graph chi-boundedness to tournament chi-bar-boundedness; no direct resolution was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $(M,\prec)$ be an ordered graph with maximum degree $1$. Then the class of $(M,\prec)$-free ordered graphs is $\chi$-bounded.

Context

This conjecture on ordered graphs arises as a sufficient condition for proving that certain tournament classes are $\operatorname{\overrightarrow{\chi}}$-bounded, via the correspondence between backedge graphs and $\chi$-boundedness established in the paper. It follows from Property 4.10 that Conjecture 4.11 would imply results about $\operatorname{\overrightarrow{\chi}}$-binding tournaments.

Source paper

Clique number of tournaments
Pierre Aboulker, Guillaume Aubian, Pierre Charbit, Raul Lopes · 2023-10-06
https://arxiv.org/abs/2310.04265