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

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

王志丹,王治文

【摘 要】摘 要 在《经济数学》等杂志上已经用穷染法给出了广义θ-图的邻点可区别全染色和邻点可区别边染色, 但方法太过繁琐. 本文结合P.N. Balister方法从结构上更为简洁的证明广义θ-图的邻点可区别染色的相关猜想. 【期刊名称】经济数学 【年(卷),期】2017(034)004 【总页数】5

【关键词】关键词 图, θ-图; 邻点可区别全染色;邻点可区别边染色 【文献来源】

https://www.zhangqiaokeyan.com/academic-journal-cn_journal-quantitative-

economics_thesis/0201236082739.html

1 引 言

定义1 u, v两点间连三条内部不交的路且至多有一条长度为1的图, 称为θ-图．[1].

定义 2 u, v两点间连k(k≥4)条内部不交的路且至多有一条长度为1的图, 称为广义θ-图, 并简记为θk(k≥4)．[1]

定义3 图G的邻点可区别全染色是一个相邻点的色集合不相等的正常全染色, 其中任意一点的色集合为点上所染的颜色和关联边上所染的颜色构成的集合, 把所用的最少颜色数称为邻点可区别全色数. [2]

定义 4 图G的邻点可区别边染色是一个相邻点的色集合不相等的正常边染色, 其中任意一点的色集合为此点相关联的边上所染的颜色构成的集合, 把所用的最少颜色数称为邻点可区别边色数．[3]