A characterization of graphs of radius-$r$ flip-width at most $2$

Abstract

The $r$-flip-width of a graph, for $r\in \mathbb{N}\cup \{\infty \}$, is a graph parameter defined in terms of a variant of the cops and robber game, called the flipper game, and it was introduced by Toruńczyk (FOCS 2023). We prove that for every $r\in (\mathbb{N}\setminus \{1\})\cup \{\infty \}$, the class of graphs of $r$-flip-width at most $2$ is exactly the class of ($C_5$, bull, gem, co-gem)-free graphs, which are known as totally decomposable graphs with respect to bi-joins.

13 pages, 3 figures