Hat guessing number and guaranteed subgraphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911748235198464 |
|---|---|
| author | Bradshaw, Peter |
| author_facet | Bradshaw, Peter |
| contents | The hat guessing number of a graph is a parameter related to the hat guessing game for graphs introduced by Winkler. In this paper, we show that graphs of sufficiently large hat guessing number must contain arbitrary trees and arbitrarily long cycles as subgraphs. More precisely, for each tree $T$, there exists a value $N = N(T)$ such that every graph that does not contain $T$ as a subgraph has hat guessing number at most $N$, and for each integer $c$, there exists a value $N' = N'(c)$ such that every graph with no cycle of length greater than $c$ has hat guessing number at most $N'$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_13422 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Hat guessing number and guaranteed subgraphs Bradshaw, Peter Combinatorics 05C15, 05C57 The hat guessing number of a graph is a parameter related to the hat guessing game for graphs introduced by Winkler. In this paper, we show that graphs of sufficiently large hat guessing number must contain arbitrary trees and arbitrarily long cycles as subgraphs. More precisely, for each tree $T$, there exists a value $N = N(T)$ such that every graph that does not contain $T$ as a subgraph has hat guessing number at most $N$, and for each integer $c$, there exists a value $N' = N'(c)$ such that every graph with no cycle of length greater than $c$ has hat guessing number at most $N'$. |
| title | Hat guessing number and guaranteed subgraphs |
| topic | Combinatorics 05C15, 05C57 |
| url | https://arxiv.org/abs/2109.13422 |