Torunczyk2023

https://www.doi.org/10.48550/ARXIV.2302.00352

@article{Torunczyk2023,
archiveprefix = {arXiv},
author = {Szymon Toruńczyk},
copyright = {Creative Commons Attribution 4.0 International},
doi = {10.48550/ARXIV.2302.00352},
eprint = {2302.00352},
month = {February},
publisher = {arXiv},
title = {Flip-width: Cops and Robber on dense graphs},
year = {2023},
}

• inf-flip-width – See radius-r flip-width for $r=\infty$.
• radius-r flip-width – The radius-$r$ flip-width of a graph $G$, denoted $fwr (G)$, is the smallest number $k \in \mathbb{N}$ such that the cops have a winning strategy in the flipper game of radius $r$ and width $k$ on $G$
• inf-flip-width $k$ upper bounds rank width by $\mathcal O(k)$ – For every graph $G$, we have $\mathrm{rankwidth}(G) \le 3 \mathrm{fw}_\infty(G)+1 …
• rank width $k$ upper bounds inf-flip-width by $2^{\mathcal O(k)}$ – For every graph $G$, we have … $3 \mathrm{fw}_\infty(G)+1 \le O(2^{\mathrm{rankwidth(G)}}).
• twin width $k$ upper bounds radius-r flip-width by $2^{\mathcal O(k)}$ – Theorem 7.1. Fix $r \in \mathbb N$. For every graph $G$ of twin-width $d$ we have: $\mathrm{fw}_r(G) \le 2^d \cdot d^{O(r)}.$
• inf-flip-width $k$ upper bounds radius-r flip-width by $\mathcal O(k)$ – By definition