一类特殊图的顶点染色及其猜想的证明

• 作者: 张祥波
• 来源期刊: 重庆工商大学学报（自然科学版）
• 学科: 数学
• 关键词: 顶点染色 最大团 第k类图 图的厚度
• 年，卷（期）: 2015,（9）
• 页码范围: 66-70
• 页数: 5页
• 分类号: O157.5
• 字数: 4062字
• 语种: 中文
• DOI: 10.16055/j.issn.1672-058X.2015.0009.017

摘要

通过研究一类特殊图的顶点染色,得到了以下结果:给出了| S|=p-3且p∈{4,5,6},图G的顶点染色数;证明了|S|＞P/2且|S| =p-3的图G不存在第p-m类图,m≥7且m是正整数;证明了|S|=p-3时,x(G)≤4θ(G) +θ2(G)-1;进一步证明了猜想x(G)≤4θ(G)+θ2(G)-1是正确的;为今后研究该猜想和图的顶点染色提供一些思想方法.