没有4-圈和6-圈的平面图的非正常2-染色

发布时间：2020-11-13 02:25

　　 图的染色理论是图论研究的核心内容,包括顶点染色,边染色,非正常染色等多个分支.实际生活中的储藏问题、调度问题以及排课表问题等都可以转化成图的染色理论来有效的解决.图的染色的定义:设G=(V,E)是一个图,k∈N~+,映射f:V→{1,2,···,k}.若对(?)uv∈E,均有f(u)≠f(u),则称f为G的一个正常点染色.如果用V_1,V_2,...,V_k表示G的顶点集的划分,则图是k-可染的当且仅当V_1,V_2,...,V_k是独立集.如果放宽这一要求就有了图的非正常染色的概念:设d_1,d_2,...,d_k是k个非负整数.如果图G的顶点集可以划分成V_1,V_2,...,V_k个子集,使得对于任意的i=1,2,...,k,V_i的点导出子图G[V_i]的最大度至多为d_i,则称图G是(d_1,d_2,...,d_k)-可染的.双圈图的非正常染色,已经有许多好的结果.本文主要研究既不含4-圈也不含6-圈的平面图的(d_1,d_2)-可染问题.得到如下结论:(i)如果G是不含4-圈和6-圈的平面图,则G是(4,4)-可染的.(ii)如果G是不含4-圈和6-圈的平面图,则G是(3,5)-可染的.
【学位单位】：江苏师范大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【文章目录】：
中文摘要
abstract
第一章 引言
    1.1 背景介绍
    1.2 平面图非正常染色的研究进展与主要结论
第二章 没有4-圈和6-圈的平面图的结构
    2.1 相关记号和概念
    2.2 结构引理
第三章 主要结论及其证明
    3.1 （4,4）-可染
    3.2 （3,5）-可染
第四章 总结
参考文献
致谢
作者简历
学位论文数据集

【参考文献】

相关期刊论文 前1条

1 徐灵姬;王应前;;既不含4-圈又不含6-圈的平面图的非正常染色[J];中国科学:数学;2013年01期

本文编号：2881589