A note on choosability in planar graphs
David Monty Berman · Czech digital mathematics library · 1982
We call a graph k-choosable if for every assignment of a list of k colors to each vertex, the graph can be properly colored so that^each vertex is colored with one of the colors on its list* Erdos, Rubin and Taylor have conjectured that every planar graph is 5-choosable.In this note we show that in a minimal counter-example to this conjecture every vertex of degree five must have a neighbor of degree at least seven* Key words: Choosability, coloring* planar graph* Classification; 05C15 Is tl] Erdos.Hubin and Taylor developed the idea of choosability in graphs* Suppose each vertex of graph G has assigned to it a list of k colors* We say that G is k-choosable or can be k-list-colored if for every assignment of lists.G has a proper coloring with each vertex assigned a color on its list* We call the minimum k for which G is k-choosable the listchromatic number of G.It is immediate that the list-chromatic number of G is at least as great as the chromatic number* That this inequality may be strict is shown by the following example: íljЗb Í1|2Î tøЉ *2 *5J OT-T U.3\The graph is 2-chromatic but the assignment of lists shown in the diagram shows that it is not 2-choosable.It might be no ted that to show that a particular graph is k-colorable one needs only to exhibit a k-coioring; to show that it is k-choosable one must show that it can be properly colored from any assignment of lists to the vertices*