论文标题
有界双宽度的图是准多态$χ$结合的
Graphs of bounded twin-width are quasi-polynomially $χ$-bounded
论文作者
论文摘要
我们证明，在\ mathbb {n} $中，每一个$ t \ in \ inthbb {n} $都有一个常数$γ_t$，以便每个具有$ t $ t $ and Clique Number $ω$的图形的图形为$ 2^{γ_t^{γ_T\ log^{4t+3}ω} $。换句话说，我们证明有界双宽度的图形类是准polynomomenth $χ$结合的。这为解决Bonnet等人的问题提供了重要的一步。 [ICALP 2021]关于它们是否是多项式$χ$结合的。
We prove that for every $t\in \mathbb{N}$ there is a constant $γ_t$ such that every graph with twin-width at most $t$ and clique number $ω$ has chromatic number bounded by $2^{γ_t \log^{4t+3} ω}$. In other words, we prove that graph classes of bounded twin-width are quasi-polynomially $χ$-bounded. This provides a significant step towards resolving the question of Bonnet et al. [ICALP 2021] about whether they are polynomially $χ$-bounded.
