论文部分内容阅读
本文研究的是连通无环的平面图.令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的完备色数,记为χvef(G),定义为使得图G是完备k-可染的最小正整数k的值.在边面染色和完备染色概念的基础上,Fabrici,Jendrol’和Vrbjarova于2016年提出了平面图弱边面染色和弱完备染色的概念.在这里,如果两条相邻边e1和e2关联于同一个面且在该面的边界上连续出现,则称这两条边是面相邻的.图G有一个弱边面k-染色是指存在一个映射π:E(G)∪F(G)→{1,2,…,k}满足:若边e1与边e2面相邻,则π(e1)≠π(e2);若面f1与面f2相邻,则π(f1)≠π(f2);若边e与面f相关联,则π(e)≠π(f).平面图G的弱边面染色数,记为Xef(G),定义为使得图G是弱边面k-可染的正整数k的最小值.Fabrici,Jendrol’和Vrbjarova证明了每个无环且无割边的连通平面图是弱边面6-可染的.同时,他们猜想:每个无环且无割边的连通平面图是弱边面5-可染的.图G是弱完备k-可染的是指存在一个映射π:V(G)∪E(G)UF(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的弱完备染色数,记为Xvef(G),定义为使得图G是弱完备kk-可染的正整数k的最小值.Fabrici,Jendrol’和Vrbjarova证明了每个无环且无割边的连通平面图是弱完备8-可染的.他们猜想:每个无环且无割边的连通平面图是弱完备7-可染的.以上两大猜想引起了研究者的兴趣.迄今为止,这两个猜想未完全解决.因此,我们有必要找出满足猜想的平面图类.本学位论文主要围绕上述猜想加以研究.学位论文共分为四个章节,如下所示:在第一章,我们给出了本文中所需用到的图论术语和基本概念,并简单概述相关染色领域中的研究进展,然后给出本文的主要结果.在第二章和第四章,我们运用数学归纳方法研究了无K4-子式的图的弱边面色数和弱完备色数.在这里,我们运用了色延拓技巧和代数等方法证明了此类平面图满足以上猜想,即:(1)每个无K4-子式的图都是弱边面5-可染的.(2)每个无K4-子式的图都是弱完备7-可染的.在第三章,我们研究了图的弱边面列表染色,并得到如下结论:(3)每个极大平面图都是弱边面列表5-可染的.需指出,结果(1)和结果(3)中的上界5均是最优的,即存在弱边面色数恰好为5的无K4-子式的图类和极大平面图类.