摘要
图Ｇ的全色数ＸＴ（Ｇ）是使得Ｖ（Ｇ）Ｕ∪Ｅ（Ｇ）中相邻或相关联的元素均染不同颜色的最少颜色数目．如果ＸＴ（Ｇ）＝△（Ｇ）＋１，则记如果ＸＴ（Ｇ）＝△（Ｇ）＋２，则记Ｇ∈．两个图Ｇ和Ｈ的联图Ｇ∨Ｈ是一个简单图，使得Ｖ（Ｇ∨Ｈ）＝Ｖ（Ｇ）∪Ｖ（Ｈ），Ｅ（Ｇ∨Ｈ）＝Ｅ（Ｇ）∪Ｅ（Ｈ）∪｛ｕｖ（Ｇ），ｖ∈（Ｈ）｝．本文证明了对任意的两个正整数ｍ和ｎ，Ｐｍ∨Ｐｎ∈当且仅当ｍ＝ｎ＝２或ｍ＝ｎ＝１，从而完全确定了两个路的联图的全色数．
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. If XT(G) =△ (G) +1,then we say ;if XT (G)=△ (G) +2,then we say . The joinof two graphs G and H,denoted by G V H,is a simple graph such that V(G V H)= V(G) ∪ V(H),E(G ∨ H) =E(G) ∪ E(H) ∪ {uv | u ∈ V(G),v ∈V(H) }. In this paper,it is proved that for any two positive integers m and n,Pm ∨Pn ∈ if and only if m=n= 2 or m=n= 1.
出处
《山东大学学报（自然科学版）》
CSCD
1996年第3期290-297,共8页
Journal of Shandong University(Natural Science Edition)
