On The Total Coloring,Entire Coloring And Choosability Coloring Of Some Graphs

Graph coloring is one of the key questions in graph theory. It comes from the study of the celebrated four color problem. It's profound significance in both theory and practice. Nowadays, as the coloring problem was widely used ig in our living, it has gradually become one of the most important areas of research scholars. Graph theory is a very active research topic, various issues were raised and have been developed developed application.In this paper, we studied the total coloring and complete coloring of the regular planar meshes-square mesh, hexagonal mesh and honeycomb mesh and the choosable coloring of the planar graph without 4-cycles, 5-cycles and intersecting triangles.First, according to the structural characteristics of regular planar meshes, the total coloring and complete coloring of square mesh, hexagonal mesh and honeycomb mesh is given, an effective coloring algorithm on the total coloring of regular planar meshes is presented. We can finish the total coloring of regular planar meshes in polynomial time. The time complexity is O (n~2). We proved the total chromatic number of the three regular planar meshes is equal to the maximum degree of the meshes plus 1. The complete chromatic number of square mesh and hexagonal mesh is equal to the maximum degree of the meshes plus 3, the chromatic number of honeycomb mesh is equal to the maximum degree of the meshes plus 4. The coloring methods is the best.Second, we constructed a new planar graph without 4-cycles, 5-cycles and intersecting triangles. In 2006, Montassier constructed a planar graph without 4-cycles and 5-cycles and intersecting triangles that is not 3-choosable (Bordeaux 3-color conjecture and 3-choosability.Discrete Mathematics, 2006, 306(4): 573-579), It has 506 vertices. This example is contradict with the Bordeaux 3-choosable conjecture: every planar graph without intersecting 3-cycles and without 5-cycles is 3-colorable. We...