Given a tournament , Aboulker, Aubian, Charbit, and Lopes (2023) defined its clique number as the minimum clique number of a backedge graph of , and raised the question: Which classes of tournaments are polynomially -bounded? Aboulker, Duron, Jacob, Kimbrough, Thomassé, and this work’s authors (2026) showed that this holds for classes of tournaments whose arc sets may be written as the union of a bounded number of comparability digraphs. What about classes of tournaments that do not admit such a decomposition? The crossing tournaments of Nguyen, Scott, and Seymour (2025) are an example of such a class, as shown in the aforementioned 2026 work; we show that nonetheless crossing tournaments are polynomially -bounded by adapting a method of Davies and McCarty (2021) and Davies (2022). We additionally show that we cannot extend this result for crossing tournaments to tournaments with chordal graphs as backedge graphs.

生成讲解博客的中文版本

生成AI智能校验的中文版本