Total coloring of embedded graphs of maximum degree at least ten  

作　　者：HOU JianFeng 1,2,WU JianLiang 2,LIU GuiZhen 2 & LIU Bin 2 1 Center for Discrete Mathematics,Fuzhou University,Fuzhou 350002,China 2 School of Mathematics,Shandong University,Jinan 250100,China 

出　　处：《Science China Mathematics》2010年第8期2127-2133,共7页中国科学：数学（英文版）

基　　金：supported by the Research Foundation for Doctor Programme (Grant No.200804220001);National Natural Science Foundation of China (Grant Nos.10871119,10971121,10901097)

摘　　要：A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color.The total chromatic number χ〃(G) is the smallest integer k such that G has a total k-coloring.In this paper,it is proved that the total chromatic number of any graph G embedded in a surface Σ of Euler characteristic χ(Σ)≥0 is Δ(G) + 1 if Δ(G)≥10,where Δ(G) denotes the maximum degree of G.A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color.The total chromatic number χ〃(G) is the smallest integer k such that G has a total k-coloring.In this paper,it is proved that the total chromatic number of any graph G embedded in a surface Σ of Euler characteristic χ(Σ)≥0 is Δ(G) + 1 if Δ(G)≥10,where Δ(G) denotes the maximum degree of G.

关 键 词：surface EULER characteristic TOTAL COLORING TOTAL CHROMATIC number 

分 类 号：O157.5[理学—数学]