2012/06/18 by Alice M. Dean, Dean, Alice M., Joan P. Hutchinson +1
Computer Science · Mathematics · #05C10 #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C10 #msc:05C15
paper · pdf · doi:10.48550/arxiv.1206.3945
12 pages, 1 figure
openalex publication_date 2012/06/18 · arxiv created 2013/01/01 · arxiv updated 2013/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph embedded on a surface Sε with Euler genus ε > 0, and let P⊆ V(G) be a set of vertices mutually at distance at least 4 apart. Suppose all vertices of G have H(ε)-lists and the vertices of P are precolored, where H(ε)=\lfloor(7 + √(24ε + 1))/(2)\rfloor is the Heawood number. We show that the coloring of P extends to a list-coloring of G and that the distance bound of 4 is best possible. Our result provides an answer to an analogous question of Albertson about extending a precoloring of a set of mutually distant vertices in a planar graph to a 5-list-coloring of the graph and generalizes a result of Albertson and Hutchinson to list-coloring extensions on surfaces.