Distant 2-Colored Components on Embeddings Part III: The General Case
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910376480735232 |
|---|---|
| author | Nevin, Joshua |
| author_facet | Nevin, Joshua |
| contents | This is the third in a sequence of three papers in which we prove the following generalization of Thomassen's 5-choosability theorem: Let $G$ be a finite graph embedded on a surface of genus $g$. Then $G$ can be $L$-colored, where $L$ is a list-assignment for $G$ in which every vertex has a 5-list except for a collection of pairwise far-apart components, each precolored with an ordinary 2-coloring, as long as the face-width of $G$ is at least $2^{Ω(g)}$ and the precolored components are of distance at least $2^{Ω(g)}$ apart. This provides an affirmative answer to a generalized version of a conjecture of Thomassen and also generalizes a result from 2017 of Dvořák, Lidický, Mohar, and Postle about distant precolored vertices. In a previous paper, we proved that the above result holds for a restricted class of embeddings which have no separating cycles of length three or four. In this paper, we use this special case to prove that the result holds in the general case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_11165 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Distant 2-Colored Components on Embeddings Part III: The General Case Nevin, Joshua Combinatorics 05C15 G.2.2 This is the third in a sequence of three papers in which we prove the following generalization of Thomassen's 5-choosability theorem: Let $G$ be a finite graph embedded on a surface of genus $g$. Then $G$ can be $L$-colored, where $L$ is a list-assignment for $G$ in which every vertex has a 5-list except for a collection of pairwise far-apart components, each precolored with an ordinary 2-coloring, as long as the face-width of $G$ is at least $2^{Ω(g)}$ and the precolored components are of distance at least $2^{Ω(g)}$ apart. This provides an affirmative answer to a generalized version of a conjecture of Thomassen and also generalizes a result from 2017 of Dvořák, Lidický, Mohar, and Postle about distant precolored vertices. In a previous paper, we proved that the above result holds for a restricted class of embeddings which have no separating cycles of length three or four. In this paper, we use this special case to prove that the result holds in the general case. |
| title | Distant 2-Colored Components on Embeddings Part III: The General Case |
| topic | Combinatorics 05C15 G.2.2 |
| url | https://arxiv.org/abs/2212.11165 |