A variation on Heawood list-coloring for graphs on surfaces
classification
🧮 math.CO
keywords
epsilonverticesheawoodlist-coloringgraphgraphslistsprove
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.