Distant 2-Colored Components on Embeddings Part I: Connecting Faces

2022/07/21 by Joshua Nevin, Nevin, Joshua
Computer Science · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2

paper · pdf · doi:10.48550/arxiv.2207.12531

openalex publication_date 2022/07/21 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28

Abstract

This is the first 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 2^Ω(g) and the precolored components are of distance 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.

Related

• Distant 2-Colored Components on Embeddings Part III: The General Case
• Distant 2-Colored Components on Embeddings Part II: The Short-Inseparable Case
• Five-List-Coloring Graphs on Surfaces: The Many Faces Far-Apart Generalization of Thomassen's Theorem
• Five-list-coloring graphs on surfaces III. One list of size one and one list of size two
• List-coloring graphs on surfaces with varying list-sizes