List-coloring graphs on surfaces with varying list-sizes

zbMATH Open1266.05028arXiv1206.3945MaRDI QIDQ1953362

Alice M. Dean, Joan P. Hutchinson

Publication date: 7 June 2013

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $G$ be a graph embedded on a surface $S_{v}arepsilon$ with Euler genus $varepsilon>0$, and let $PsubseteqV(G)$ be a set of vertices mutually at distance at least 4 apart. Suppose all vertices of $G$ have $H(varepsilon)$-lists and the vertices of $P$ are precolored, where $H(varepsilon)=Biglfloorfrac7+sqrt24varepsilon+12Bigfloor$ 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.

Full work available at URL: https://arxiv.org/abs/1206.3945

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

graphs on surfaceslist-coloringHeawood number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (4)

Five-list-coloring graphs on surfaces. II: A linear bound for critical graphs in a disk. ⋮ Hyperbolic families and coloring graphs on surfaces ⋮ Approximating List-Coloring on a Fixed Surface ⋮ Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs

This page was built for publication: List-coloring graphs on surfaces with varying list-sizes