图的无圈边色数及相关参数的研究

With the rapid development of information science and computer science, as an important theoretical basis, graph theory and combinatorial mathematics get lots of attentions and extensive research from international maths and the theory of computer attaches, graph coloring theory has a center position in graph theory. Based on the current results, we study the following problems: (1) We study the acyclic edge coloring of graphs. Around the famous acyclic edge coloring conjecture, we focus on the acyclic chromatic index of 4-regular graphs and planar graphs. We try to present a clear answer to the question that whether that conjecture holds for 4-regular graphs, give a new upper bound for the acyclic chromatic index of planar graphs, and try to characterize the outerplanar graphs with maximum degree 4 according to the acyclic chromatic index; (2) We study the egde-face coloring of plane graphs. To be exact, we focus on the edge-face chromatic number of planar graph with maximum degree 4 and maximum degree 5 and the edge-face choosability of planar graph with maximum degree 8. As one of the hot topics at home and abroad, our researchs can greatly enrich the research results of the subjects related, promote some of the famous open problems to solve or partially solve, and have important theoretical significance and application value. Five papers will be completed within three years, with more than three cited by SCI.

随着信息科学与计算机科学的迅猛发展，图论和组合数学作为其重要理论基础得到国际数学界和理论计算机界的高度重视和广泛研究,图的染色理论更是图论的重要内容。本项目在现有的工作基础上,深入研究以下几个问题：(1) 研究图的无圈边染色问题。围绕著名的无圈边染色猜想,重点研究4-正则图和平面图的无圈边色数。考虑4-正则图是否满足该猜想；确定平面图的无圈边色数的更好的上界；研究外可平面图的无圈边色数,力争根据无圈边色数,刻画最大度为4的外可平面图；(2) 研究平面图的边-面染色问题。考虑最大度为4和5的平面图的边-面染色问题；研究最大度为8的平面图的边-面选择数。本项目的研究内容是国内外研究的热点课题之一,能丰富相关课题的研究成果,促进一些著名难题的解决或部分解决,有重要的理论意义和应用价值。拟在三年内完成五篇论文,三篇以上被SCI收录。

图的染色理论是图论的重要内容，也是图论的起源之一，其研究来源于著名的四色问题，具有重要的实际意义和理论意义。如今，它在生产管理、军事、交通运输、计算机网络等许多领域都有着重要的应用。图G的一个正常k-边染色是指G的边到集合{1,2,⋯,k}的一个映射，使得任意两条相邻的边染不同的颜色。无圈边染色最早是由Fiamčіk在1978年提出的。无圈k-边染色是指图G的一个正常k-边染色，使得在此染色下图G不产生双色圈。图G的无圈边色数定义为a’(G)=min{k│G是无圈k-边可染的}。Fiamčіk和Alon，Sudakov以及Zaks先后于1978年和2001年分别提出了著名的无圈边色数猜想，即对任何图G，a’(G)≤∆(G)+2。诸多学者对此猜想展开了一系列的研究。特别地，找寻一般图的无圈边色数的上界、验证哪些图类满足这个猜想等就变得非常有意义。自立项以来，本项目组致力于该课题的研究，我们分别验证了不含三角形的4-正则图和含有三角形的4-正则图都满足该猜想，结合已有结论，得到4-正则图是满足该猜想的。相应的两个成果均发表在杂志《Bulletin of the Malaysian Mathematical Sciences Society》上。近期，我们还验证了不含相交三角形的平面图和外1-可平面图是满足无圈边染色猜想的。此外，本项目还研究了一些相关的问题，并证得了：(1) g(G)≥6的平面图是(1,0)-松弛强边(3Δ(G)-1)-可选的。相应的结果发表在杂志《Discrete Mathematics, Algorithms and Applications》上。这个结论改进了已有的一个结果：g(G)≥7且Δ(G)≥4的平面图是(1,0)-松弛强边(3Δ(G)-1)-可选的；(2) 若G为只含有一个闭内面的2-连通外平面图，且该闭内面是一个偶面，那么图G的(2,1)-点面标号数为6当且仅当G是坏的。相应的成果已被杂志《浙江师范大学学报(自然科学版)》接收。本项目组共计发表相关论文3篇，其中2篇被SCI检索。本项目取得的这些研究成果在一定程度上丰富了图的边染色相关问题的研究内容。