平面图的弱边面（列表）染色和弱完备染色

发布时间：2021-03-13 06:02

　　本文研究的是连通无环的平面图.令G=（V,E,F）是一个平面图,其中V表示点集,E表示边集,F表示面集.图G是边面k-可染的是指存在一个映射π:E（G）∪f（G）→{1,2,…,k}满足:任意相邻边e1和e2,有π（e1）≠π（e2）;任意相邻面f1和f2,有π（f1）≠π（f2）;任意相关联边面e和f,有π（e）≠π（f）.如果图G是边面k-可染的,则称图G有一个k-边面染色.图G的边面色数,记为χef（G）,定义为使得图G是边面k-可染的最小正整数k的值.平面图边面染色的概念是由Jucovicc和Fiamccik在1970年前后分别独立提出.1973年,Kronk和Mitchem提出了完备染色的概念.图G是完备k-可染的是指存在一个映射π:V（G）∪E（G）∪F（G）→{1,2,…,k}满足:任意相邻点v1和v2,有π（v1）≠π（v2）;任意相邻边e1和e2,有π（e1）≠π（e2）;任意相邻面f1和f2,有π（f1）≠π（f2）;任意相关联的点边面v,e和f,有π（v）≠π（e）,π（v）≠π（f）且π（e）≠π（f）.如果图G是完备k-可染的则称图G有一个完备k-染色.图G的... 

【文章来源】：浙江师范大学浙江省

【文章页数】：61 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 基本概念
    1.2 平面图的弱边面（列表）染色和弱完备染色的研究概况
    1.3 本文主要结果
4-子式的图的弱边面染色">第二章 无K₄-子式的图的弱边面染色
    2.1 一些记号
4-子式的图的结构性质">    2.2 无K₄-子式的图的结构性质
4-子式的图是弱边面5-可染的证明">    2.3 无K₄-子式的图是弱边面5-可染的证明
第三章 极大平面的弱边面列表染色
    3.1 相关概念
    3.2 极大平面图及其对偶图结构性质
    3.3 定理3.1的证明
4-子式的图的弱完备染色">第四章 无K₄-子式的图的弱完备染色
    4.1 符号说明
4-子式的图是弱完备7-可染的证明">    4.2 无K₄-子式的图是弱完备7-可染的证明
第五章 总结与展望
参考文献
攻读学位期间取得的研究成果
致谢



本文编号：3079700