Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2212.10506 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917618641797120 |
|---|---|
| author | Nevin, Joshua |
| author_facet | Nevin, Joshua |
| contents | This is the second in a sequence of three papers in which we prove the following generalization of Thomassen's 5-choosability theorem: Let $G$ be a 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 this paper we prove that the above result holds for a restricted class of embeddings, i.e. those embeddings which satisfy certain triangulation conditions and do not have separating cycles of length at most four. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_10506 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Distant 2-Colored Components on Embeddings Part II: The Short-Inseparable Case Nevin, Joshua Combinatorics 05C15 G.2.2 This is the second in a sequence of three papers in which we prove the following generalization of Thomassen's 5-choosability theorem: Let $G$ be a 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 this paper we prove that the above result holds for a restricted class of embeddings, i.e. those embeddings which satisfy certain triangulation conditions and do not have separating cycles of length at most four. |
| title | Distant 2-Colored Components on Embeddings Part II: The Short-Inseparable Case |
| topic | Combinatorics 05C15 G.2.2 |
| url | https://arxiv.org/abs/2212.10506 |