Three-Colorability Of Planar Graphs

Let G=(V, E) be a graph with the set of vertices V and the set of edges E. A mappingφ:V→{1,…,k} is called a k-coloring of G ifφ(u)≠φ(v) whenever uv∈E.If G admits a k-coloring, then G is said to be k-colorable. Call a graph planar if it can be embedded into the plane so that its edges meet only at their ends; such a particular embedding of a planar graph is called a plane graph.In 1959, Grotzsch proved that planar graphs without 3-cycles are 3-colorable. In 1976, Steinberg conjectured every planar graph without 4 and 5-cycles is 3-colorable. People have done a serial of research on Steinberg conjecture. In 1993, Erdos suggested to study a weak form of this problem, asking if there exists an integer k such that every planar graph without cycles of length from 4 to k is 3-colorable. Abbott and Zhou (1991) proved that such a k exists and k≤11. This result was later improved to k≤9 by Borodin (1996) and, independently, Sanders and Zhao (1995), and to k≤7 by Borodin et al. (2005). These prove that every planar graph without 4,5,6 or 7-cycle is 3-colorable. In chapter 2, we consider the 3-coloring of planar graphs without adjacent cycles, and prove that planar graphs without adjacent 7--cycles are 3-colorable by extendability lemmas and identification. Obviously, it improves the result obtained by Borodin et al. (2005).As a further study of Steinberg conjecture, in 2006, Xu proved that planar graphs without 5 and 7-cycles and without adjacent triangles are 3-colorable. In 2009, Borodin et al. found a counterexample of the result of Xu (Xu has done a correction of his proof later), and gave a new proof. In chapter 3 of this paper, we think of other ways to prove the same result. In chapter 4, we prove:planar graphs without 6 and 8-cycles, and 3-cycles not adjacent to 3 or 4-cycles, and 4-cycles not adjacent to 5-cycles are 3-colorable. This result improve a result by Wang and Chen:planar graphs without 4,6,8-cycles are 3-colorable.