Sanders 9700750 This award provides funds for a joint research project involving Daniel Sanders and Yue Zhao. The objective of the research proposed here is to attempt to solve several problems which are related to graphs embedded in surfaces using a relatively new and unexploited technique, aalled the Discharging Method. These problems include: (i) Vizing's Planar Graph Conjecture; (ii) the Total Coloring Conjecture for planar graphs; (iii) the Entire Coloring Conjecture; (iv) the Cyclic Coloring Conjecture; (v) the Nine Color Conjecture; (vi) further investigation on the k-Walk Conjecture, which the principal investigators solved in 1996; (vii) vertex reconstruction of 4-connected planar graphs, which is a special case of the Vertex Reconstruction Conjecture; (viii) edge reconstruction of triangulations of surfaces, which is a special case of the Edge Reconstruction Conjecture. Some of these problems have been around for more than thirty years, but still remain unsolved. Recently, the principal investigators have successfully solved several problems related to (i)--(vi) by using the Discharging Method. It seems that other methods which were used to attack several of the problems mentioned above have stalled, and that the Discharging Method indeed provides a far more general and powerful tool for various problems. The principal investigators also intend to continue their search for new areas of graph theory where the Discharging Method can be applied. This research is in the area of combinatorics. One of the goals of combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.
