Robert Hickingbotham - Cop-width, flip-width and strong colouring numbers

dmtcs:14976 - Discrete Mathematics & Theoretical Computer Science, May 7, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.14976
Cop-width, flip-width and strong colouring numbersArticle

Authors: Robert Hickingbotham

Cop-width and flip-width are new families of graph parameters introduced by Toruńczyk (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.


Volume: vol. 27:2
Section: Graph Theory
Published on: May 7, 2025
Accepted on: May 4, 2025
Submitted on: December 20, 2024
Keywords: Mathematics - Combinatorics

Consultation statistics

This page has been seen 608 times.
This article's PDF has been downloaded 490 times.