摘要
图染色是图论的重要组成部分,它有着一定的理论意义和实际应用背景.给出了直积图P_m∧S_n、P_m∧F_n与P_m∧W_n的第一类弱全染色数,并分别给出了构造性的证明,进而验证了这些图对第一类弱全染色猜想成立.
Graph coloring is an important part of the graph theory,which has a certain theoretical and practical application background. In this paper,we give the first kind weakly total coloring number of direct product graph P_m∧S_n,P_m∧F_n and P_m∧W_n by using a constructive method,and then verify these graphs to set up the first weak total coloring conjecture.
引文
[1]BUMIS A C,SCHELP R H.Vertex-distinguishing proper edge-colorings[J].Graph Theory,1997,26(2):73-82.
[2]BALISTER P N,GYORI E,LEHEL J,et al.Adjacent vertex distinguishing edge-colorings[J].Siam J Discrete Math,2007,21(1):237-250.
[3]张婷,李沐春,徐宝根,等.关于Cm×C5n的全染色数和邻强边色数[J].兰州交通大学学报(自然科学版),2007,26(6):124-126.
[4]LI J W,ZHANG Z F,CHEN X E,et al.D(β)-vertex-distinguishing proper edge-coloring of graphs[J].Acta Math Sinca,2006,49(3):703-708.
[5]ZHANG Z F,QIU P X,XU B G,et al.Vertex-distinguishing total coloring of graphs[J].Arscomb,2008,87:33-45.
[6]张忠辅,李敬文,陈祥恩.图的距离不大于的任意两点可区别的全染色[J].中国科学,2006,A49(10):1430-1440.
[7]ZHANG Z F,LIU L Z,WANG J F.Adjacent strong edge coloring of graphs[J].Appl Math Lett,2002,15(5):623-626.
[8]ZHANG Z F.On the first kind weak total coloring of graphs[EB/OL].[2008-10-12].http://202.201.18.40:8080/mas5/.
[9]CHEN X E,ZHANG Z F.Adjacent Vertex-distinguishing total chromatic number of K2n+1-E(2K2)[J].兰州大学学报(自然科学版),2005,41(6):102-105.
[10]于玲,叶永升.路和圈的联的Wiener指数[J].淮北师范大学学报(自然科学版),2011,32(1):1-3.
[11]BONDY J A,MURTY U S R.Graph theory with applications[J].Macmillan,1976,28(1):237-238.
[12]张忠辅,王建芳.关于图的全着色的一个综述[J].数学进展,1992,21(4):390-397.
[13]BALISTER N,PIORDAN O M,SCHELP R H.Vertex-distinguishing proper edge colorings of graphs[J].Graph Theory,2003,42(2):95-105.
[14]ZHANG Z F,CHEN X E,LI J W,et al.On adjacent-vertex-distinguishing total coloring of graphs[J].Sci China,2005,A48(3):289-299.
[15]HATAMI H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J].J Combinatorial Theory,2005,B95(2):246-256.
[16]WANG H Y.On the adjacent vertex-distinguishing total chromatic numbers of the graphs withΔ(G)=3[J].J Combinatorial Optimization,2007,14(1):87-109.