Centered colorings and weak coloring numbers in minor-closed graph classes
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914391326195712 |
|---|---|
| author | Hodor, Jędrzej La, Hoang Micek, Piotr Rambaud, Clément |
| author_facet | Hodor, Jędrzej La, Hoang Micek, Piotr Rambaud, Clément |
| contents | Let $\mathcal{C}$ be a proper minor-closed class of graphs. Given the minors excluded in $\mathcal{C}$, we determine the maximum $q$-centered chromatic number and the maximum $q$th weak coloring number of graphs in $\mathcal{C}$ within an $\mathcal{O}(q)$-factor. Moreover, when $\mathcal{C}$ excludes a planar graph, we determine it within a constant factor. Our results imply that the $q$-centered chromatic number of $K_t$-minor-free graphs is in $\mathcal{O}(q^{t-1})$, improving on the previously known $\mathcal{O}(q^{h(t)})$ bound with a large and non-explicit function $h$. We include similar bounds for another family of parameters, the fractional treedepth fragility rates. All our bounds are proved via the same general framework. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13097 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Centered colorings and weak coloring numbers in minor-closed graph classes Hodor, Jędrzej La, Hoang Micek, Piotr Rambaud, Clément Combinatorics Discrete Mathematics Let $\mathcal{C}$ be a proper minor-closed class of graphs. Given the minors excluded in $\mathcal{C}$, we determine the maximum $q$-centered chromatic number and the maximum $q$th weak coloring number of graphs in $\mathcal{C}$ within an $\mathcal{O}(q)$-factor. Moreover, when $\mathcal{C}$ excludes a planar graph, we determine it within a constant factor. Our results imply that the $q$-centered chromatic number of $K_t$-minor-free graphs is in $\mathcal{O}(q^{t-1})$, improving on the previously known $\mathcal{O}(q^{h(t)})$ bound with a large and non-explicit function $h$. We include similar bounds for another family of parameters, the fractional treedepth fragility rates. All our bounds are proved via the same general framework. |
| title | Centered colorings and weak coloring numbers in minor-closed graph classes |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2603.13097 |