Acta mathematica scientia,Series B ›› 1996, Vol. 16 ›› Issue (2): 162-169.

• Articles • Previous Articles     Next Articles

ON THE TOTAL COLORING OF GRAPH GH

Xu Baogang   

  1. Math. of Dept., Shandong University, Jinan 250100, China
  • Received:1994-03-21 Revised:1995-02-23 Online:1996-06-25 Published:1996-06-25

Abstract: The total chromatic number XT(G) of graph G is the least number of colors assigned to VE(G) such that no adjacent or incident elements receive the same color.Given graphs G1,G2, the join of G1 and G2, denoted by G1G2, is a graph G, V(G)=V(G1)∪V(G2) and E(G)=E(G1)∪E(G2) ∪{uv|uV(G1), vV(G2)}. In this paper, it's proved that if v(G)=v(H), both Gc and Hc contain perfect matching and one of the followings holds:(i)Δ(G)=Δ(H) and there exist edge eE(G), e'∈E(H) such that both G-e and H-e' are of Class l; (ii)Δ(G)<Δ(H) and there exixst an edge eE(H) such that H-e is of Class 1, then, the total coloring conjecture is true for graph GH.

Key words: graph, join of graphs, total chromatic number

Trendmd