Odd coloring graphs with linear neighborhood complexity
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908827071283200 |
|---|---|
| author | Davies, James Hatzel, Meike Knauer, Kolja McCarty, Rose Ueckerdt, Torsten |
| author_facet | Davies, James Hatzel, Meike Knauer, Kolja McCarty, Rose Ueckerdt, Torsten |
| contents | We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if $\mathcal{G}$ is the class of all circle graphs, or if $\mathcal{G}$ is any class with bounded twin-width, bounded merge-width, or a forbidden vertex-minor, then $\mathcal{G}$ is $χ_{\mathrm{o}}$-bounded. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08926 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Odd coloring graphs with linear neighborhood complexity Davies, James Hatzel, Meike Knauer, Kolja McCarty, Rose Ueckerdt, Torsten Combinatorics Discrete Mathematics We prove that any class of graphs with linear neighborhood complexity has bounded improper odd chromatic number. As a result, if $\mathcal{G}$ is the class of all circle graphs, or if $\mathcal{G}$ is any class with bounded twin-width, bounded merge-width, or a forbidden vertex-minor, then $\mathcal{G}$ is $χ_{\mathrm{o}}$-bounded. |
| title | Odd coloring graphs with linear neighborhood complexity |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2506.08926 |