3-LIST-COLORING PLANAR GRAPHS OF GIRTH 5

摘要

We prove that every planar graph of girth at least 5 is 3-choosable. It is even possible to precolor any S-cycle in the graph. This extension implies Grotzsch's theorem that every planar graph of girth at least 4 is 3-colorable. (C) 1995 Academic Press, Inc. [References: 5]