Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.00991 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918432681754624 |
|---|---|
| author | Higgins, Cecelia |
| author_facet | Higgins, Cecelia |
| contents | We prove a descriptive version of Brooks's theorem for directed graphs. In particular, we show that, if $D$ is a Borel directed graph on a standard Borel space $X$ such that the maximum degree of each vertex is at most $d \geq 3$, then unless $D$ contains the complete symmetric directed graph on $d + 1$ vertices, $D$ admits a $μ$-measurable $d$-dicoloring with respect to any Borel probability measure $μ$ on $X$, and $D$ admits a $τ$-Baire-measurable $d$-dicoloring with respect to any Polish topology $τ$ compatible with the Borel structure on $X$. We also prove a definable version of Gallai's theorem on list dicolorings for directed graphs by showing that any Borel directed graph of bounded degree whose connected components are not Gallai trees is Borel degree-list-dicolorable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_00991 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Measurable Brooks's Theorem for Directed Graphs Higgins, Cecelia Logic Combinatorics We prove a descriptive version of Brooks's theorem for directed graphs. In particular, we show that, if $D$ is a Borel directed graph on a standard Borel space $X$ such that the maximum degree of each vertex is at most $d \geq 3$, then unless $D$ contains the complete symmetric directed graph on $d + 1$ vertices, $D$ admits a $μ$-measurable $d$-dicoloring with respect to any Borel probability measure $μ$ on $X$, and $D$ admits a $τ$-Baire-measurable $d$-dicoloring with respect to any Polish topology $τ$ compatible with the Borel structure on $X$. We also prove a definable version of Gallai's theorem on list dicolorings for directed graphs by showing that any Borel directed graph of bounded degree whose connected components are not Gallai trees is Borel degree-list-dicolorable. |
| title | Measurable Brooks's Theorem for Directed Graphs |
| topic | Logic Combinatorics |
| url | https://arxiv.org/abs/2405.00991 |