k-剖分图的k-次幂的着色数

发布时间：2024-02-15 03:11

　　图G是一个有限图,κκ是一个非负整数.图G的κκ-剖分图Sκ(G)就是将图G的每一条边用一条κκ长路来替代得到的图;即将图G的每条边插入(-1)个新顶点得到的图.图G的κ-次幂图就是图G中所有距离小于等于κ的点进行连边得到的图.图G的κ-次幂剖分图就是将图G的每一条边用一条κ长路来替换之后,此时距离小于等于κ的点进行连边得到的图;即将图G的每条边插入(κ-1)个新顶点后,距离小于等于κ的点连边得到的图.在此定义下图G的全图T(G)我们就记为S2(G)2.图G的着色数记为χ(G),全着色数记为χ"(G).本文主要研究S3(G)3的着色数.Rosenfeld[11]和Vijayaditya[14]分别证明了,对于最大度小于等于三的图G,χ"(G)5.基于这一理论,本文证明了对于最大度小于等于三的图G,χ(S3(G)3)≤ 7.

【文章页数】：21 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 引言
    1.1 基本定义
    1.2 研究背景及现状
    1.3 本文的主要工作
第二章 预备知识
第三章 主要定理及证明
参考文献
硕士期间发表及完成论文清单
致谢



本文编号：3899099