图的可区别染色理论与算法的研究

图染色理论在诸如物理、化学、计算机科学、网络理论等许多领域有着广泛的应用。起源于频率分配问题及计算机科学描述空间数据库中点与点之间关系的实际问题，图的(邻)点可区别正常边染色、(邻)点可区别全染色及其相关猜想是受到当前国际著名图论专家(如Bollobás等)重视的研究课题。本项目挖掘组合、代数、概率方法,创新思路，探索新工具，比如利用"色集事先分配"、"共一色"等新方法对图的这4类染色做进一步探讨，以期有更深理论成果，程度较大地部分解决每个相应猜想；将这4类染色的研究与算法相结合，给出这4类染色的回溯、分支定界等算法，探索可区别染色的DNA算法，分析算法的有效性及可行性，并进行仿真实验，对阶数不超过10的图确定4类确切的色数；借助于算法找到子图的可区别色数超过母图的相应色数的若干例子，探讨子图的可区别色数不超过母图的相应色数的条件。

1985 年，Harary F 等人开始研究图的点可区别一般边染色；Chartrand G,Jacobson M， Lehel J 等人于1986 年 研究图的可允许的一般边染色（即顶点被关联边的颜色之和可区别的一般边染色，所使用的颜色是从1开始的相继的正整数）所需要的颜色的最少数目即图的非正规强度；Burris A C，Schelp R H 于 1993年和Cerny J， Hornak M， Sotak R 于1995年分别独立地提出图的点可区别正常边染色，取得了许多重要的成果。此后，图的可区别染色受到越来越多的学者的关注。本项目主要针对图的（邻）点可区别正常边染色、（邻）点可区别正常全染色等进行研究。我们对满足一定条件的完全四部图、完全五部图以及最大度为9， 10，11的平面二部图的邻点可区别正常边染色问题进行了探讨；对许多图类的点可区别正常边色数进行确定，得到了诸如“p(≥2)阶完全图与q(≥4)阶星的合成图的点可区别正常边色数等于pq”等重要结论，确定了完全图与星的合成图的点可区别正常边色数的确切值；对15阶及17阶的完全图删去一个三角形子图的三条边后所得到的图、5阶空图与完全图的联图、5阶圈与完全图的联图等图类的邻点可区别全色数的确切值给予确定，所得结果均支持AVDTC猜想；对子母图的点可区别全色数之间的关系进行了研究，得到了“对任意正整数r，总存在最大度为r的图G，使G的某个子图的点可区别全色数大于G的点可区别全色数”，探索了一个图与该图删去一条边得到的图的点可区别全色数之间的重要关系，给出了一个具有较多边数的奇阶图的点可区别全色数等于它的完全母图的点可区别全色数的两个充分条件，利用这两个充分条件可以确定出大量的使点可区别全色数等于最大度加3的图类。此外，我们对图的点可区别E-全染色、点可区别IE-全染色、点可区别I-全染色、点可区别一般边染色、邻点可区别的各种未必正常全染色进行了探讨。所得到的成果丰富和发展了图的可区别染色理论，对可区别染色理论的进一步研究具有一定的参考意义。