1-可平面图的若干染色问题研究

发布时间：2023-04-26 03:31

　　图的染色理论起源于十九世纪中叶被提出的著名的“四色问题”,是图论中最重要的研究课题之一。近些年来,随着离散型事物的数学模型应用的日益广泛,图的染色已不仅限于对图的点染色、边染色和全染色,各种特征的染色概念相继出现,从而使图的染色理论研究内容也越来越丰富。本文旨在研究特殊的1-平面图的一些有限制条件的染色问题。若无特别说明,本文所研究的图均为简单的,有限的,无向的非空图。如果一个图G能画在平面上使得任意两条边之间不产生内部交叉(即任何两条边之间仅在端点相交),则称图G称为可平面图。上述这样一种画法称为G的一个平面嵌入。平面图是指可平面图的某个平面嵌入。如果一个图G能画在平面上使得它的每条边至多被交叉一次,则称这个图为1-可平面图。满足上述条件的1-可平面图的平面嵌入称为1-平面图。设G是一个图的某个平面嵌入,如果G中出现交叉点,那么每个交叉点都可以与G中的四个顶点(即形成此交叉点的两条相交边的四个端点)的点集建立对应关系,记为∧。设a,b是G中的两个交叉点,如果∧(a)∩∧(=(?),则称a与b是相互独立的。如果图G能画在平面上使得其任何两个交叉点是独立的,则称图G为IC-可平面图。满足...

【文章页数】：99 页

【学位级别】：博士

【文章目录】：
致谢
摘要
Abstract
变量注释表
1 绪论
    1.1 基本概念与符号
    1.2 图的几类染色及相关猜想
    1.3 论文主要结论
2 全染色
    2.1 不含3-圈的1-平面图的全染色
3 邻和可区别全染色
    3.1 IC-平面图的邻和可区别全染色
    3.2 IC-平面图的邻和可区别全染色的紧界
4 无圈边染色
    4.1 IC-平面图的无圈边染色
5 邻和可区别边染色
    5.1 不含3-圈的1-平面图的邻和可区别边色数
6 总结与展望
    6.1 1-平面图与IC-平面图的围长
    6.2 进一步研究的问题
参考文献
附录A
作者简历
学位论文数据集



本文编号：3801653