关于广义θ—图的邻点可区别染色的简单证明

王志丹+王治文

摘 要 在《经济数学》等杂志上已经用穷染法给出了广义θ-图的邻点可区别全染色和邻点可区别边染色， 但方法太过繁琐. 本文结合P.N. Balister方法从结构上更为简洁的证明广义θ-图的邻点可区别染色的相关猜想.

关键词 图， θ-图； 邻点可区别全染色；邻点可区别边染色

中图分类号 O157.5 文献标识码 A

Abstract In the Journal of Quantitative Economics and so on， the general method is used to give the adjacent vertex distinguishing total coloring and the adjacent vertex distinguishing edge coloring of the general θ-graph. But the methods are too complicated. In this paper， P.N.Balister method is used to prove the relative conjectures of the adjacent vertex distinguishing coloring of the general θ-graph.

Key words graph， θ-graph， adjacent vertex distinguishing total-coloring，adjacent vertex distinguishing edge-coloring

参考文献

[1] 张和平，欧阳克智. θ-图及其线图的联结数[J].兰州大学学报（自科版），1992，28（3）：6-11.

[2] 张忠辅，陈祥恩，李敬文，等.关于图的邻点可区别全染色[J].中国科学A，2004， 34（5）：574-583.

[3] ZHANG Z F，LIU L Z， WANG J F. Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters，2002，15（5）：623-626.

[4] 閆丽宏，王治文，张忠辅.广义θ-图的邻点可区别的全染色（英文）[J].经济数学， 2007，24（1）：103-106.

[5] BALISTER P N， GYORI E， LEHEL J，et al.Adjacent vertex distinguishing edge-colorings[J]. Siam Journal on Discrete Mathematics，2007，21（1）：237-250.

[6] BONDY J A，MURTY U S R.Graph theory with applications[M].New York： The Macmillan Press Ltd，1976.endprint