关于奇阶同阶图的联图的全着色

ON THE TOTAL COLORING OF GRAPH GVH WITH γ(G)=γ(H)=1(MOD 2)

图G的全色数x_T(G)是使得VE(G)中相邻接或相关联的元素均着不同颜色的最少颜色数。证明了:如果ν(G)=ν(H),存在υ(?)V(G),υ'(?)V(H)使得G^c—υ和H^c—υ'都含有完美对集且△(G)=△(H)并存在e(?)E(G—υ),e'(?)E(H—υ'),使得G—e和H—e'都是第一类图,或△(G)<△(H)且存在e(?)E(H—υ')使得H—e'是第一类图,则x_T(GVH)≤△(GVH)+2g.

The total chromatic number XT(G) of a graph G is the least number of colors assigned to VE(G) such that no adjacent or incident elements receive the same color. It is proved that if γ(G) =γ(H), and there exist v∈V(G),v' ∈V(H) such that both Gc-v and Hc-v' contain perfect matching and one of the followings holds: ( I ) △(G)=△(H) and there exist edge e ∈E(G),e' ∈E(H) such that vV({e}),v' V({e' }), both G-e and H-e' are of Class 1,( Ⅱ)A(G)<△(H) and there exists an edge e∈E(H) such that v' F({e}) and H-e is of Classl, then the total coloring conjecture is true for graph G V H.