Total Coloring Of Graphs Embedded In Surfaces Of Nonnegative Euler Characteristic

A k-total-coloring of a graph G is a map from V(G)∪E(G) to {1,2,..., k}, such that no two adjacent or incident elements receive the same color. The total chromatic number x"(G) is the smallest integer k such that G has a k-total-coloring. As early as1960s, Vizing and Behzad independently conjectured that for any graph G,△(G)+1≤x"(G)≤△(G)+2. This conjecture was known as Total Coloring Conjecture. This conjecture has been confirmed for general graphs with△(G)≤5.For planar graphs, the only open case is△(G)=6. It is interesting to notice that many planar graphs are proved to be x"(G)=△(G)+1, i.e., the exact result has been obtained. Up to date, For each planar graph with△(G)≥9, x"(G)=△(G)+1. However, for planar graphs with4≤△(G)≤8, no one has found counterexamples that are not (△(G)+1)-totally-colorable. So, Yingqian Wang et al. conjectured that planar graphs with△(G)>4are (△(G)+1)-totally-colorable. This paper mainly discusses total coloring of graphs embedded in surfaces of nonnegative Euler characteristic. Graphs considered in this paper are graphs embedded in surfaces of nonnegative Euler characteristic, and they are simple, finite, undirected and nonempty. In the second section of this paper, we obtain five results:Let G be a graph embedded in a surface Σ of Euler characteristic x(Σ)≥0with maximum△and girth g.(1) There is an integer t(>g) such that G has no cycles of length from g+1to t. Then the total chromatic number of G is△+1if one of the following conditions holds.(a)△≥6,(g,t)=(4,6);(b)△≥5,(g,t)=(4,17).(2)△=3,each vertex of G is incident with at most one g-cycle and there is an integer t(>g) such that G has no cycles of length from g+1to t.Then x"(G)=△+1if one of the following conditions holds.(a) g=5,t≥31;(b)g=6,t≥18;(c)g=7,t≥14;(d) g=8,t≥12;(e)g=9,t≥10.(3) x"(G)=△+1in each of the following cases:(a)△≥9;(g)△≥7,g≥4;(c)△≥5,g≥5;(d)△≥4,g≥6;(e)△≥3,g≥10.(4)△(G)=4and G contains no k-cycle,and no intersecting3-cycles,where k∈{4,5,...,11},then x"(G)=△+1.(5)△(G)=8and G contains no intersecting3-cycles,then x"(G)=△+1.