Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2306.15206 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909354283761664 |
|---|---|
| author | Chang, Yeonsu Ko, Sejin Kwon, O-joung Lee, Myounghwan |
| author_facet | Chang, Yeonsu Ko, Sejin Kwon, O-joung Lee, Myounghwan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_15206 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A characterization of graphs of radius-$r$ flip-width at most $2$ Chang, Yeonsu Ko, Sejin Kwon, O-joung Lee, Myounghwan Combinatorics 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. |
| title | A characterization of graphs of radius-$r$ flip-width at most $2$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2306.15206 |