3-Choosability Of Planar Graphs

In 1979, P. Erdo|¨s et al conjectured that every planar graph is 5-choosable and there are planar graphs which are not 4-choosable. More than one decade later, the conjecture was settled by Voigt and Thomassen. More precisely, Voigt constructed a planar graph which is not 4-choosable, and Thomassen proved that every planar graph is 5-choosable. A natural problem on choosability of planar graphs is to determine whether a given planar graph is 3-choosable, or 4-choosable. Soon later, Gutner proved that the problem is NP-hard. Recently, Mickae|¨l Montassier asked: what are the sufficient conditions for a planar graph to be 3-choosable? This dissertations concerns 3-choosability of planar graphs.Following precedent works, this dissertations studies 3-choosability problem of planar graphs. The main results obtained in this dissertations may be summarized as follows:(1) Every planar graph without 4-, 5- and 9-cycles, and without triangles at distance less than 3 is 3-choosable.(2) Every planar graph without cycles of length 4, 6, 8, or 9 is 3-choosable.(3) Every planar graph without cycles of length 4, 7, 8, or 9 is 3-choosable.