前言

1985 年, Harary F 等人开始研究图的点可区别一般边染色; Chartrand G, JacobsonM, Lehel J 等人于1986 年研究图的可允许的一般边染色(即顶点被关联边的颜色之和可区别的一般边染色，所使用的颜色是从1开始的相继的正整数)所需要的颜色的少数目即图的非正规强度; Burris A C, Schelp R H于 1993年和 Cˇ erny?J, Horˇn?ak M, Sot?ak R 于1995年分别独立地提出图的点可区别正常边染色, 取得了许多重要的成果. 特别是2002年以来, 张忠辅教授相继提出图的邻点可区别正常边染色，邻点可区别正常全染色, 点可区别正常全染色等新的图染色概念之后,图的可区别染色受到越来越多学者的重视.

本书是作者在多年给研究生讲授“图的可区别染色”课程所写讲稿的基础上整理而成的. 图的可区别染色不是一种染色, 而是许多种染色的总称. 本书就是介绍各种可区别染色, 包括点可区别正常边染色(第1 章)、邻点可区别正常边染色(第2 章)、点可区别正常全染色(第3 章)、邻点可区别正常全染色(第4 章)、D(d)–点可区别正常边染色(第5 章前3 节)、D(d)–点可区别正常全染色(第5 章后3 节)、点强可区别正常全染色(第6 章第1 节)、邻点强可区别正常全染色(第6 章第2 节)、邻和可区别正常边染色(第6 章第3 节)、邻和可区别正常全染色(第6 章第4 节)、邻点可区别无圈边染色(第6 章第5 节)、可区别的未必正常的染色(第6 章第6 节给出了分类). 书中介绍的都是可区别染色方面的重要成果或者作者非常感兴趣的素材. 许多结论的证明过程融入了作者的理解与体会.

本书第6 章第6 节(即本书后一节)所涉及的边染色及全染色都是未必正常的, 仅对可区别的未必正常的染色做了分类, 而其余各章节所涉及的边染色及全染色都是正常的.

本书每一章都有该章所涉及的参考文献.人们研究可区别染色主要围绕以下几个方面: , 确定一些图类的某种染色的色数(即确定对一些图类进行某种染色所需的少颜色的数目);

第二, 研究某类图是否满足关于某种染色的猜想(我们可以看到几乎每种可区别染色都有相应的猜想);

第三, 给出某种染色的色数的上界;

第四, 研究某类图的某种色数随着阶增大的变化趋势;

第五, 研究某种染色的某个特定问题, 比如寻找子图的某种可区别色数不超过其母图的相应色数的条件. 而对于普通的正常点(边, 全)色数来说, 子图的色数一定不超过相应的母图的色数. 而对于可区别染色来说, 情况并非如此.在研究可区别染色理论时, 人们采用的方法通常有: 构造具体染色、组合分析、反证法与原理结合、数学归纳法、加点加边法、共一色法、色集事先分配法、填装法、放电法、概率方法、利用组合零点定理、利用某个群中的元素为颜色来染色, 等等.

我们会看到, 尽管关于各种可区别染色, 国内外学者已有非常丰富的成果, 但是许多猜想并没有得到解决(除D(d)–VDEC 猜想及D(d)–VDTC 猜想均已有反例).

图的可区别染色理论是图论的一个分支. 而图论既属于组合数学, 也属于运筹学. 图论组合问题有一个特点, 问题的表述相当容易(就像四色问题的表述一样,一位中学生就会明白是怎么回事), 但是解决起来相当难. 希望对可区别染色理论感兴趣的学者能创新方法, 开拓思路, 以推动可区别染色理论的进一步发展.如果对图的可区别染色感兴趣的初学者及相关研究生觉得本书还有可取之处, 那么笔者就满足了.笔者于2003 年在张忠辅教授的指导下开始了图的可区别染色的研究. 尽管先师已于2010年7月作古, 但是他提出的有关可区别染色的若干问题及猜想已被许多学者所研究, 他的思想及方法启示着后人, 他的坚持不懈地进行科学研究的风范永远是我学习的榜样. 我从事可区别染色的研究, 得益于张忠辅教授的指导,因此作者对先师的感激发自肺腑.

西北师范大学数学与统计学院的领导对本书编写工作给予了极大的支持; 同时北京大学许进教授、兰州大学张和平教授、南开大学李学良教授、巴黎十一大李皓教授、山东大学吴建良教授、中国科学院闫桂英教授、浙江师范大学王维凡教授、暨南大学樊锁海教授、西北师范大学姚兵教授和姚海元副教授、兰州交通大学李敬文教授和文飞博士等对本书编写给予了极大的鼓励与帮助; 在书稿的Latex录入过程中, 我的研究生高毓平、胡志涛、魏甲静、张芳红、郭靖、郭虹园、黄小佳、师瑾等同学帮了我很大的忙. 在此对上述领导、专家、同学一并表示衷心感谢! 本书的编写与出版得到了国家自然科学基金(项目批准号: 61163037)的资助, 作者非常感谢!限于水平, 尽管作者做了很大努力, 但是书中定有许多不足之处, 敬请读者批评指正.

陈祥恩

2015 年6 月于西北师范大学