图的强边染色和强全染色以及相关专题

Graph coloring has occupied the center of graph theory. It has many applications in computer science, information science, industrial production and business management, and many other areas. It has increasingly attracted attentions of researchers in other branches of mathematics and in theoretical computer science. This project will study the four conjectures on neighbor distinguishing and neighbor sum distinguishing edge and total colorings. We propose to improve the known upper bounds on the chromatics numbers of those four colorings, to verify those conjectures for some families of graphs such as 2-degenerate graphs, planar graphs, and to extend the known results to list version. The study of this project will help completely solve some of the four conjectures, to advance the research in graph coloring theory and network irregularities, and to help solve other major problems in graph theory.

图的染色理论一直占据图论的中心地位，在计算机科学、信息科学、工业生产与企业管理等诸多领域都有着广泛的应用，日益得到国际数学界和理论计算机科学界的高度重视。本项目拟围绕邻点可区分与邻和可区分的边染色与全染色的四个猜想展开研究：改进这些色数的已知上界；拟对更多的特殊图类，特别是平面图和2退化图，证明这些猜想成立；将邻和可区分的边染色与全染色的一些已知结果推广到列表染色。希望通过此项目的研究，能彻底解决其中的某些猜想，并以此推动图染色理论和网络不规则性等领域的研究与发展，促进一些重要或重大图论问题的解决。

本项目主要研究了一些特殊图类的邻点可区别全染色、邻和可区别边染色、邻和可区别全染色及其相应的列表染色，验证了邻点可区别全染色猜想对最大度为4的图成立，给出了图的邻点可区别全色数与色数、边色数之间的关系；研究了平面图的(k,d)-染色以及与图的染色密切相关的整数流问题、带号图的模流和群连通度，改进了Seymour and Thomassen的结果，并对一类带号图验证了著名Bouchet’s 6-流猜想。此外，本项目还考虑了可嵌入到曲面上的图的最大度、图的欧拉宽度和图的平面Ramsey数等相关参数。所取得的成果丰富了图的染色等相关理论，对推动图论中一些重要问题的解决有着重要意义。