A variation on Heawood list-coloring for graphs on surfaces
From MaRDI portal
Publication:3189190
zbMATH Open1301.05086arXiv1302.7055MaRDI QIDQ3189190
Publication date: 9 September 2014
Abstract: We prove a variation on Heawood list-coloring for graphs on surfaces, modeled on Thomassen's planar 5-list-coloring theorem. For epsilon>0 define the Heawood number to be H(epsilon)=Floor((7+Sqrt[24*epsilon+1])/2). We prove that, except for epsilon=3, every graph embedded on a surface of Euler genus epsilon>0 with a distinguished face F can be list-colored when the vertices of F have (H(epsilon)-2)-lists and all other vertices have H(epsilon)-lists unless the induced subgraph on the vertices of F contains the complete graph on H(epsilon)-1 vertices.
Full work available at URL: https://arxiv.org/abs/1302.7055
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items (1)
This page was built for publication: A variation on Heawood list-coloring for graphs on surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189190)
