论文部分内容阅读
令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的边面色数xef(G),定义为使得G是边面k-可染的最小的正整数k的值.这个概念最早由Jucovi(c)和Fiam(c)(i)k在1970年前后分别独立提出. 在正常边面染色定义的基础上,2016年,Fabrici等人首次提出了弱边面染色的概念.图G是弱边面k-可染的是指存在一个映射π:E(G)∪F(G)→{1,2,…,k},使得任意两个相关联的边和面,任意两个相邻的面,以及任意两条面相邻的边都染不同的颜色.这里,我们称两条相邻边e1和e2是面相邻的当它们关联同一个面且在该面的边界上连续出现时.平面图G的弱边面染色数是指G是弱边面k-可染的正整数k的最小值,用(x)ef(G)表示.Fabrici等人证明了每个无环且无割边的连通平面图是弱边面6-可染的.同时,他们猜想:每个无环且无割边的连通平面图是弱边面5-可染的.此猜想引起了研究者们的极大兴趣.目前为止,该猜想仍未完全解决.因此,研究该染色问题是十分有意义的.本学位论文主要围绕以上猜想加以研究.学位论文共分为四个章节,如下所示: 第一章节,我们首先给出本文中所要用到的图论的基本概念,然后简述相关领域的研究现状,最后给出本文的主要结果. 第二章节,第三章节以及第四章节,我们运用数学归纳方法分别研究了哈林图、极大平面图、外平面图这三类特殊的平面图.具体来讲,我们运用色延拓技巧,组合计数,颜色置换等方法证明了如下三个结果满足以上猜想,即: (1)每个哈林图都是弱边面5-可染的. (2)每个极大平面图都是弱边面5-可染的. (3)每个外平面图都是弱边面5-可染的. 需要指出,以上三个结果中的上界5均是最优的.