Title: Cop-width, flip-width and strong colouring numbers Show Chinese title

Title: 边翻数、翻转数和强着色数

Abstract: Cop-width and flip-width are new families of graph parameters introduced by Toru\'nczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and twin-width. In this paper, we bound the cop-width and flip-width of a graph by its strong colouring numbers. In particular, we show that for every $r\in \mathbb{N}$, every graph $G$ has $\text{copwidth}_r(G)\leq \text{scol}_{4r}(G)$. This implies that every class of graphs with linear strong colouring numbers has linear cop-width and linear flip-width. We use this result to deduce improved bounds for cop-width and flip-width for various sparse graph classes. Show Chinese abstract

Abstract: Cop-宽度和翻转-宽度是图参数的两个新族，由托鲁ńczyk（2023年）引入，它们推广了树宽、退化性、广义着色数、 clique-宽度和双宽。 在本文中，我们通过图的强着色数来限制cop-宽度和翻转-宽度。特别是，我们证明了对于每个 $r\in \mathbb{N}$，每个图 $G$有 $\text{copwidth}_r(G)\leq \text{scol}_{4r}(G)$。 这意味着每个强着色数具有线性的图类也具有线性的cop-宽度和线性的翻转-宽度。 我们利用这个结果推导出各种稀疏图类的cop-宽度和翻转-宽度的改进界限。