与图的顶点染色数有关的几个问题

• 作者: 张祥波
• 来源期刊: 高师理科学刊
• 学科: 数学
• 关键词: 顶点染色数 第k类图 最大团 图的厚度
• 年，卷（期）: 2016,（3）
• 页码范围: 17-20
• 页数: 4页
• 分类号: O157.5
• 字数: 2984字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-9831.2016.03.005

摘要

设x(G)是无向简单图G(V,E)的顶点染色数,证明了:若|S|＞P/2且|S|=p-m,则图G不存在第p-q类图,其中:q≥2m+1,m≥3且m∈z+;若|S|=p-4,则x(G)≤ p-3;若|S|=p-4,则x(G)≤4θ(G)+θ2(G)-1.