平面图与无爪图的团染色研究

发布时间：2025-02-13 19:53

　　图的染色理论是图论研究的热点问题之一.而均匀染色理论又是染色理论的进一步发展,在化学、生物学、计算机科学、工业生产和企业管理等领域中有着广泛的应用.图的团染色是图的点染色的一个变体,又称之为弱染色.本文主要研究的是图的团染色问题和图的均匀团染色问题.研究图的团染色问题和图的均匀团染色问题有着重要的应用背景和理论价值.第一章首先阐述了本文所需要的基本概念和定义.其次介绍了本课题的研究意义.最后对近十几年团染色的研究进展做了系统的梳理.第二章主要研究了平面图的团染色问题.Mohar和ˇkrekovski已证明了平面图是3-团可染色的(Electr.J.Combin.6（1999）,#R26).在本章节中,我们运用归纳法进一步证明了任意平面图是3-团可染色的,并且设计了一个3-团染色平面图的线性时间算法（以上结果已经发表在《Operations Research Letters》杂志）.第三章主要研究了无爪图的均匀团染色问题.Bacs′o和Tuza证明了以下定理:除了阶数大于3的无弦奇圈,最大度至多为4的无爪连通图是2-团可染色的,并且在（9）²)时间内可以找到一个2-团...

【文章页数】：41 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
符号表
第一章 绪论
    1.1 基本概念与定义
    1.2 课题介绍及研究意义
    1.3 团染色问题的研究进展
第二章 平面图的团染色问题
    2.1 平面图的团染色
    2.2 线性时间算法
第三章 无爪图的均匀团染色问题
    3.1 无爪图的均匀团染色
    3.2 线性时间算法
    3.3 结论
参考文献
攻读硕士学位期间完成及发表的论文
致谢



本文编号：4034031