2022/12/20 by Joshua Nevin, Nevin, Joshua
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Colored #Combinatorics #Combinatorics (math.CO) #Conjecture #FOS: Mathematics #G.2.2 #Generalization #Genus #Graph #Law #Limits and Structures in Graph Theory #Mathematics #Omega #Physics #Vertex (graph theory)
paper · pdf · doi:10.48550/arxiv.2212.10506
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2022/12/20 · openalex created_date 2023/01/04 · openalex updated_date 2026/08/06
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.