Cop-width, flip-width and strong colouring numbers
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912371460538368 |
|---|---|
| author | Hickingbotham, Robert |
| author_facet | Hickingbotham, Robert |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_05874 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Cop-width, flip-width and strong colouring numbers Hickingbotham, Robert Combinatorics 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. |
| title | Cop-width, flip-width and strong colouring numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.05874 |