两类特殊平面图的全染色

来源 :河北工业大学 | 被引量 : 0次 | 上传用户:qmdx521
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
给 定 一 个 图 G, G 的 fc-全 染 色 是 指 至 多 用 k 种颜色,对 G 的顶点和边同时进行着色,使得相邻的两个元素(点和边)染不同的颜色. G 的 全 色 数 X"( G )是 指 使 得 G 有 一 个 &-全染色的最小整数 k.众所周知,H. Vizing和 Behzad在 1965年分别独立的提出了全染色猜 想 £Total Coloring Conjecture), 简称T C C ,即 对 任 意 图 G,都满足X"(G) < A (G ) +2 .到目前为止,除了最大度为6 的平面图的全染色问题还没有被解决,其他平面图均被证明了满足全染色猜想.本文应用了一种不同于“差值转移法” 的全新证明方法证明了最大度A 至少为8 且 不 含 4- 圈的平面图是(A + 1)-全可染的,并应用此方法证明了最大度为 6 且每个顶点至多关联L 」个三角形的平面图是8-全可染的.
其他文献
  树模型近年来已引起物理学、概率论及信息论界的广泛兴趣。树指标随机过程已成为近年来发展起来的概率论的研究方向之一。在概率论的发展过程中,对强偏差定理的研究一直占
梯度投影算法已经被应用于解决信号重构问题。首先介绍了GPSR-BB投影梯度法,该方法将l1极小化问题转化为一个界约束二次规划问题(BCQP)来进行信号重构。通过对GPSR-BB方法线
  选址问题是运筹学中的一个非常经典的问题,其数学模型是一个典型的0-1规划。鉴于该问题的组合优化特点,尽管其求解方法有很多,但很少有能够求解大型问题的有效算法。本文利