边染色临界图的相关问题的研究

P.G.Tait proved that the Four-Color Conjecture is equivalent to the statement that every simple 2-edge-connected 3-regular planar graph is 3-edge-colorable. This gives rise to the concept of the edge-coloring of graphs.It has become an important branch of graph theory due to its theoretical significance and its essential role in the applied sciences, while critical graphs play a very important role in the study of the edge-coloring of graphs. This program will center on the related problems of critical graphs..First，we study the new properties of critical graphs and planar critical graphs on the base of VAL. Then, we study the classification of 2-edge-connected planar graphs with maximum degree 3 and prove M.O.Albertson's conjecture for the case that there are at least three 2-vertices, and study the average degree of critical graphs and prove that the average degree of any critical graph is almost its maximum degree minors 1 by the discharging mathod, and study the classification of planar graphs and prove that every planar graph with maximum degree six is of class one by Eular's formular and the discharging method. We also give some sufficient conditions that critical graphs contain 1-factors or almost 1-factors by the conditions that graphs contain 1-factors or almost 1-factors.

P.G.Tait证明四色猜想等价于任一2-边连通立方平面图的边都可以用三种颜色正常染色，由此产生了图的边染色的概念。由于它的重要的理论意义和广泛的应用背景，图的边染色理论已成为图论的一个重要分支，而在图的边染色研究中临界图起着很重要的作用。本项目的研究主要围绕临界图的相关问题而展开。. 首先在Vizing邻接引理的基础上，进一步研究一般临界图和平面临界图的的性质。研究2-边连通的最大度是3的平面图的分类问题，对于至少有3个2-点的情况证明M.O.Albertson的猜想为真；利用discharging方法研究临界图的平均度，证明其平均度接近其最大度减一；利用欧拉公式和discharging方法研究平面图的分类，证明最大度是6的平面图都是第一类的；利用一般图存在1-因子或几乎1-因子的条件给出临界图存在1-因子或几乎1-因子的充分条件。

起源于四色猜想的图的染色理论和图的拓扑指数以及图的控制理论是图论的重要研究分支，具有重要的理论价值和应用背景。在国家自然基金项目(No.11271365)的资助下，本项目主持人和项目组成员的研究工作主要围绕以下方面展开：关于边染色临界图的若干猜想、图的距离染色、图的动态染色和r-hued染色、图的无圈点染色、平面图的强边染色、1-平面图的无圈边染色和点染色、图的离心距离和以及图的若干控制参数。得到如下结果：.1、给出了边染色临界图的一些新性质，利用这些新性质改进了最大度为11或12的临界图的平均度的下界。2、研究了Vizing的关于临界图的独立数的猜想，改进了Woddall的关于独立数上界的结果。3、关于图的动态染色和r-hued染色，研究了图的动态色数与其去掉一条边或一个点后的动态色数之间的关系，给出了它们之差的上下界并刻划了极图；给出了K4-minor free 图的r-hued色数的一个紧的上界和r-hued列表色数的一个上界；证明了对于围长至少是5的平面图G，当r是3到7之间的整数时，G的r-hued色数不超过r+11。4、关于平面图的强边染色，给出了围长和最大度至少是5的平面图的强边色数的一个上界。5、关于1-平面图的无圈边染色和点染色，给出了无三角形的1-平面图的无圈边色数的一个上界，并且证明了无4-圈或相邻5-点的1-平面图都是5-可染色的。6、关于图的无圈点染色，证明了最大度是6的图都是无圈10-可染色的，改进了Hervé Hocquard （2011）的主要结果。7、关于图的离心距离和，刻画了给定最大度的具有最大EDS的树，刻画了控制数是3的具有最大EDS的树，刻画了给定独立数的具有最大和最小EDS的树，刻画了给定匹配数的具有最大EDS的树。8、对于图的控制问题，给出了寻找块图和一些特殊树的2-step控制集的O（m）次算法；给出了完全二部图和轮图的符号全控制数的精确值；证明了边全控制问题对于最大度是3的平面图、无向路图、一些弦图和一些树是NP-完备的等等。9、研究了二氧化碳排放现状，为制定应对气候变化国家方案及实现我国二氧化碳减排目标提供决策与对策参考；构建我国雾霾污染治理控制机制，为我国的大气污染治理提出具有科学性和可操作性的对策建议。