子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色,且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值,记作χ′_(2-snd)(G).采用反证法证明了:若图G是子立方图,则χ′_(2-snd)(G)≤7.

图的D(2)-点可区别一般边染色

引入了图的D(β)-点可区别一般边染色,并对β=2的情形做了讨论,得到了路,圈,星,双星,扇,轮的D(2)-点可区别一般边色数,对于2距离色数等于3及4的图的D(2)-点可区别一般边色数做了探讨,特别研究了具有稳定2距离4着色的图的D(2)-点可区别一般边染色.文中提出了一个相关猜想和一个公开问题.

图的距离不大于2的点可区别边色数的一个上界

用图的概率方法中的第一矩量原理和Markov不等式得到图的距离不大于2的区别边色数的一个上界对最大度为d,有n个点的简单图G,d≥3有χ2′-vd(G)≤3/2nd(d-1).