Production Of Maximal Plane Graphs And Chromatic Numbers Of Some Special Graphs

Graph Theory is one of the important components of Discrete Mathematics. The color problem is the early and significant field in Graph Theory and in the recently years it is a hot point all along, but it has not been solved until now. Its application is limited since the effective arithmetic even the good approximate arithmetic for the chromatic number of a graph has not been found to this day. It needs farther research.This paper introduces the current situation and significance of the research on the color problem at first. And then an adding-vertex method is presented for the production of maximal plane graphs through a study on the structures of these graphs, and it proves credible. Next this paper shows the necessary and sufficient condition of that the chromatic number of a simple connected graph is not more than 2. Afterward it is proved that a simple plane graph is a spanning subgraph of a maximal plane graph, so the chromatic number top of a simple plane graph is the chromatic number of the correlative maximal plane graph. Subsequently it is revealed that 3 is the chromatic number of a maximal plane graph in which the degree of every vertex is an even number. At last, based on the proof of that every maximal plane graph is 5-colorable, some maximal plane graphs which are produced by the first and second means of the adding-vertex method prove 4-colorable by the mathematics induction and a conjecture is given for the others. If this conjecture holds, every maximal plane graph could be 4-colorable, and ulteriorly the Four Color Theorem would be proved.