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

项目名称： 图的可区别染色理论与算法的研究

项目编号： No.61163037

项目类型： 地区科学基金项目

立项/批准年度： 2012

项目学科： 自动化技术、计算机技术

项目作者： 陈祥恩

作者单位： 西北师范大学

项目金额： 49万元

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

中文关键词： （邻）点可区别边染色；（邻）点可区别全染色；点可区别E (IE;I)--全染色；点可区别一般边染色；邻点可区别的各种未必正常全染色

英文摘要：

英文关键词： (adjacent) vertex distinguishing edge coloring；(adjacent) vertex distinguishing total colorings；vertex distinguishing E (IE;I)-total colorings；point distinguishing general edge colorings；AVD various not necessarily proper total colorings