Three-Colorability And Three-Choosability Of Planar Graph

A k-coloring of G is a mappingφ:V→{1,...,k} such thatφ(u)≠φ(v) whenever uv∈E. G is said to be k-colorable if G admits a k-coloring.A list-assignment of a graph G is a function L which assigns each vertex v∈V(G) a list of available colors L(v). If G has a proper coloringφsuch thatφ(v)∈L(v) for every vertex v, then we say thatφis an L-coloring of G, or G is L-colorable. We say that G is k-choosable if it is L-colorable for every list-assignment L with |L(v)|≥k for all v∈V(G).In 1979, P. Erdos 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. Gutner proved that these two problems are NP-hard.In 1976, Steinberg asked whether every planar graph without 4- and 5-cycles is 3-colorable. As a relaxation of this problem, Erdos asked if there exists an integer k such that every planar graph without cycles of length from 4 to k is 3-colorable? In 1995, Borodin et al. proved that the planar graphs without cycles of length 4 to 7 are 3-colorable. As far as we know, it is the best result of Erdos' problem. It seems far to settle Steinberg's conjecture. Following previous works, this thesis studies the 3-colorability and 3-choosability problems of planar graphs, by extendability lemmas, discharging and identification. The main results obtained in this dissertation may be summarized as follows:(1) Every planar graph without cycles of length 4, 6,7 or 9 is 3-choosable;(2) Every planar graph without cycles of length 4, 5, 8, or 9 is 3-choosable;(3) Every planar graph without 4-, 7- and 9-cycles is 3-colorable.