Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2308.15721 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912076344066048 |
|---|---|
| author | Hickingbotham, Robert Kang, Dong Yeap Oum, Sang-il Steiner, Raphael Wood, David R. |
| author_facet | Hickingbotham, Robert Kang, Dong Yeap Oum, Sang-il Steiner, Raphael Wood, David R. |
| contents | The clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $c$ such that every graph $G\in\mathcal{G}$ has a $c$-colouring where each monochromatic component in $G$ has bounded size. We study the clustered chromatic number of graph classes $\mathcal{G}_H^{\text{odd}}$ defined by excluding a graph $H$ as an odd-minor. How does the structure of $H$ relate to the clustered chromatic number of $\mathcal{G}_H^{\text{odd}}$? We adapt a proof method of Norin, Scott, Seymour and Wood (2019) to show that the clustered chromatic number of $\mathcal{G}_H^{\text{odd}}$ is tied to the tree-depth of $H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_15721 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Clustered Colouring of Odd-$H$-Minor-Free Graphs Hickingbotham, Robert Kang, Dong Yeap Oum, Sang-il Steiner, Raphael Wood, David R. Combinatorics The clustered chromatic number of a graph class $\mathcal{G}$ is the minimum integer $c$ such that every graph $G\in\mathcal{G}$ has a $c$-colouring where each monochromatic component in $G$ has bounded size. We study the clustered chromatic number of graph classes $\mathcal{G}_H^{\text{odd}}$ defined by excluding a graph $H$ as an odd-minor. How does the structure of $H$ relate to the clustered chromatic number of $\mathcal{G}_H^{\text{odd}}$? We adapt a proof method of Norin, Scott, Seymour and Wood (2019) to show that the clustered chromatic number of $\mathcal{G}_H^{\text{odd}}$ is tied to the tree-depth of $H$. |
| title | Clustered Colouring of Odd-$H$-Minor-Free Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.15721 |