图的邻点可区别边染色及相关问题研究

Graph coloring theory has a center position in graph theory. It has important applications in optimization, computer science, and network design ect.. Based on the current results, we study the following problems: 1. We study the adjacent vertex distinguishing edge coloring of graphs. We try to solve or partially solve the adjacent vertex distinguishing edge chromatic number of planar graphs; characterize the adjacent vertex distinguishing edge chromatic number of planar graphs with large maximum degree; and characterize the adjacent vertex distinguishing edge chromatic number of planar graphs without some short cycles; 2. We study some other coloring problems, such as vertex distinguishing total coloring and acyclic edge coloring. We try to give a new upper bound for the adjacent vertex distinguishing total chromatic number of graphs; study the relationship between the adjacent vertex distinguishing edge chromatic number and the adjacent vertex distinguishing total chromatic number; and study the acyclic edge chromatic number of planar graphs and generalize some related results. There are only few results on the adjacent vertex distinguishing edge coloring of planar graphs. Our researchs greatly enrich the content of adjacent vertex distinguishing coloring problem.

图的染色理论在图论研究中占有重要的地位, 在最优化, 计算机理论, 网络设计等方面都有着重要的应用. 本项目在现有工作基础上, 深入研究以下几个问题: (一) 研究图的邻点可区别边染色问题. 力争解决或部分解决平面图的邻点可区别边色数; 刻画高度平面图的邻点可区别边色数; 并刻画不含短圈的平面图的邻点可区别边色数; (二) 研究其他一些染色内容: 如图的邻点可区别全染色, 无圈边染色等. 争取给出图的邻点可区别全色数的上界, 探讨邻点可区别边色数与邻点可区别全色数之间的关系; 研究平面图的无圈边色数并推广相关的结果. 目前, 有关平面图的邻点可区别边染色问题的研究结果还比较少. 本项目所研究的问题极大地丰富了邻点可区别染色的研究内容.

图的染色理论在图论研究中占有重要的地位; 在最优化, 计算机理论, 网络设计等方面都有着重要的应用. 本项目主要研究讨论了平面图的邻点可区别边染色、邻和全染色、距离2-点可区别边色数等内容. 项目组负责人以及项目组成员严格执行既定的研究工作计划，获得了以下一些研究内容：1. 证明了最大度至少为12的平面图的邻点可区别边色数至多为Δ+2; 2. 刻画了最大度至少为16的平面图的邻点可区别边色数; 3. 刻画了不含3-圈且最大度至少为12的平面图的邻点可区别边色数; 4. 证明了最大度至少为7的二部平面图的邻点可区别边色数至多为Δ+1; 5. 给出了外平面图的距离2-点可区别边色数的上界min{2Δ, Δ+8}. 特别的, 当G是二部外平面图时，其距离2-点可区别边色数至多为Δ+2; 6. 给出树的(2,1)-全标号等于Δ+1的一些充分条件; 7. 证明了最大度至少为14的平面图的邻和可区别全色数至多为Δ+2. 项目组负责人以及项目组成员共计发表相关论文9篇, 其中SCI检索论文6篇. 在本项目的基础上, 项目组成员还获得两项相关的国家自然科学基金青年基金项目. 目前, 有关平面图的邻点可区别边染色问题的研究结果还比较少. 本项目所取得的这些结果极大地丰富了邻点可区别染色的研究内容.