Limits of degeneracy for colouring graphs with forbidden minors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914116621303808 |
|---|---|
| author | Norin, Sergey Turcotte, Jérémie |
| author_facet | Norin, Sergey Turcotte, Jérémie |
| contents | Motivated by Hadwiger's conjecture, Seymour asked which graphs $H$ have the property that every non-null graph $G$ with no $H$ minor has a vertex of degree at most $|V(H)|-2$. We show that for every monotone graph family $\mathcal{F}$ with strongly sublinear separators, all sufficiently large bipartite graphs $H \in \mathcal{F}$ with bounded maximum degree have this property. None of the conditions that $H$ belongs to $\mathcal{F}$, that $H$ is bipartite and that $H$ has bounded maximum degree can be omitted. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_13715 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Limits of degeneracy for colouring graphs with forbidden minors Norin, Sergey Turcotte, Jérémie Combinatorics 05C07, 05C15, 05C83 Motivated by Hadwiger's conjecture, Seymour asked which graphs $H$ have the property that every non-null graph $G$ with no $H$ minor has a vertex of degree at most $|V(H)|-2$. We show that for every monotone graph family $\mathcal{F}$ with strongly sublinear separators, all sufficiently large bipartite graphs $H \in \mathcal{F}$ with bounded maximum degree have this property. None of the conditions that $H$ belongs to $\mathcal{F}$, that $H$ is bipartite and that $H$ has bounded maximum degree can be omitted. |
| title | Limits of degeneracy for colouring graphs with forbidden minors |
| topic | Combinatorics 05C07, 05C15, 05C83 |
| url | https://arxiv.org/abs/2304.13715 |