pith. sign in

arxiv: 1302.7055 · v2 · pith:PHWNU6QDnew · submitted 2013-02-28 · 🧮 math.CO

A variation on Heawood list-coloring for graphs on surfaces

classification 🧮 math.CO
keywords epsilonverticesheawoodlist-coloringgraphgraphslistsprove
0
0 comments X
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.