Coloring Graphs On Surfaces And Related Topics

The problems of coloring graphs on surfaces and the minimal forbidden subgraphs on surfaces are important research subjects in topological graph theory. The theory of embedded graphs has many applications, such as physics, chemistry, theoretical computer science.For each fixed surface and each natural number k≥8, Dirac observed that there are only finitely many k-color-critical graphs on S. Mohar and Thomassen proved that for a surface S of Euler genus γ>3, every7-color-critical graph on S has less that69(γ-2) vertices. Using Euler formula and the critical-graphs methods of Gallai, we improve this result and give a simple proof that the number of7-color-critical graphs is finite.The classical theorem of Brooks tell us if G is a simple connected graph and is neither an odd cycle nor a complete graph, then its chromatic number is at most△(G), where△(G) is the maximum degree of the graph G. It follows that the chromatic number of any6-regular graphs embedded on the torus is at most6. Thomassen proved that the chromatic number of any6-regular graphs embedded on the torus is5-colorable unless G=K7or G=T11. By analying the structure of graphs embedded on the Klein bottle, we prove that the chromatic number of any6-regular graphs embedded on the Klein bottle is at most5.Kuratowski theorem characterizes planar graphs in terms of forbidden subgraphs, a graph cannot be embedded in the plane if and only if it con-tains a subgraph which is isomorphic to a subdivision of K5or K3,3. Glover, Huneke, and Wang constructed103minimal forbidden subgraphs for the projective plane, moreover Archdeacon proved that this list is complete. We study the forbiden subgraphs on the torus, give some constructions for min-imal forbidden subgraphs on the torus. We also study the obstructions for toroidal embedding extensions.