Three-Colorability Of Planar Graphs

Let G=(V, E, F) be a graph with the set of vertices V and the set of edges E and the set of faces F. It is well known that every planar graph is4-colorable. Then people’s interest has turned into the problem on3-colorability. As early as1959, Grotzsch proved a well known Three Color Theorem:every triangle-free planar graph is3-colorable. In1970, Havel asked:does there exist a constant k such that every planar graph with distance between triangles at least K is3-colorable? In1976, Steinberg conjectured:every planar graph with neither cycles of length4nor cycles of length5is3-colorable. In spite of many efforts to Steinberg conjectured, no evidence shows that they can be settled in the future not far away. In1991, Erdos asked:if there exists an integer k such that every planar graph without cycles of length from4to K is3-colorable? Also in1991, Abbott and Zhou proved that such a k exists and k≤11. This result was later on improved to k≤9by Borodin and, independently, by Sanders and Zhao, and to k≤7by Borodin et al. Recently researches have shown that:The plane graph without4-,j-,k-,ι-cycles is3-colorable,5≤j≤k≤ι≤9. It is a phased result in the progress of researching3-colorability.In the following researching, we would do naturally some work on3-colorability of plane graph without4-, j-, k-cycles,5≤j≤k. Baogang Xu, Borodin et al. proved that every planar graph with neither cycles of length5or7nor adjacent triangles is3-colorable, independently. As a corollary of this result, planar graphs without4-,5-and7-cycles are3-colorable. In chapter2, we prove a result which is closer to the Steinberg’s conjecture than the corollary mentioned above. Let G be a planar graph without4-and5-cycles, then G is3-colorable if it has no (k,7)-chords for each k∈ (3,6,7), where a (k,7)-chord is a chord of a cycle of length7+k-2whose two ends divide the cycle into two paths, one of which is of length6and the other of length k-1.At the cross of the roads to the problem of Havel asked and Steinberg conjectured above, Borodin and Raspaud proposed the Bordeux Conjecture in2003:planar graphs with neither cycles of length5nor intersecting (adjacent) triangles are3-colorable, and made the first breakthrough in this direction which proved that every planar graph with neither cycles of length5nor triangles at distance less than4is3-colorable. This result was later strengthened to no triangles at distance less than3in2004by Borodin and Glebov and, independently, in2007by Xu. Now the result has been improved to no tri-angles at distance less than2by Borodin and Glebov. To study3-colorability of planar graphs, it seems that no reasons is required for lacking cycles of some special length. Namely we may allow that cycles of any length may appear in our planar graphs and the distance of cycles is considered. Therefore, Montassier et al. showed that every pla-nar graph without cycles of length at most five at distance less than four is3-colorable. Borodin, Montassier and Raspaud asked:is every planar graph without adjacent cycles of length at most five3-colorable? In chapter3, we show that:every planar graph without cycles of length at most five at distance less than two is3-colorable.During the researching on3-colorability of plane graph without4-, j-, k-cycles,5≤j≤k, professor Baogang Xu has been the first person solving the problem, and proved that every planar graph with neither cycles of length5or7nor adjacent triangles is3-colorable(This result also has been obtained by famous expert in the area of coloring Borodin et al. using different method). Clearly, this result is more closer to the Steinberg conjecture. As a corollary, it gives the first certain result about3-colorable of plane graph without three different kinds of cycles, i.e.,every plane graph without4-,5-,7-cycles is3-colorable. In this direction, the second result and the third result considering the cases that graph without4-,6-,8-cycles and without4-,7-,9-cycles are proved by Weifan wang, Min Chen and Huajing Lu, Yingqian Wang et al., respectively. Except the three results above, there is no correct examples showing that whether it is3-colorable or not for the planar graphs, which have triangle but no4-cycle or other two kinds of cycles of different length. In chapter4, inspired by the basic works before, We have proved the fourth certain result:planar graphs without4-,6-and9-cycles are3-colorable.