科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-09-02· math.CO

Bounded Twin-Width Tournaments are $\dchi$-Bounded

Chaoliang Tang, Junchi Zhang

原始摘要(英文原文)· Original abstract
For a tournament $T$ and a vertex ordering $\prec$, let $T^{\prec}$ be the graph of backward arcs in $\prec$. The diclique number of a tournament is $\domega(T)=\min_{\prec}ω(T^{\prec})$, and the dichromatic number is $\dchi(T)=\min_{\prec}χ(T^{\prec})$. We prove a mixed parameter transfer theorem: for all $k$ and $r$, if $\tww(T)\le k$ and $ω(T^{\prec})\le r$, then the ordered twin-width of $(T^{\prec},\prec)$ is bounded by a function of $k$ and $r$. The proof combines the regular-semigrid theorem for ordered graphs with permutation-encoding obstructions to bounded twin-width in tournaments. Together with polynomial $χ$-boundedness of graphs of bounded twin-width, this implies that tournaments of bounded twin-width are $\dchi$-bounded by $\domega$, resolving a conjecture of Aboulker, Aubian, Charbit, and Lopes.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

Bounded Twin-Width Tournaments are $\dchi$-Bounded — 科研速览 Science Skim