图的可区别染色引论
作者： 陈祥恩
出版社：中国科学技术出版社 2015年11月
简介：
图的可区别染色不是一种染色, 而是许多种染色的总称. 本书就是介绍各种可区别染色, 包括点可区别正常边染色(第1章)、 邻点可区别正常边染色(第2章)、 点可区别正常全染色(第3章)、 邻点可区别正常全染色(第4章)、 D(d)-点可区别正常边染色(第5章前3节)、 D(d)-点可区别正常全染色(第5章后3节)、 点强可区别正常全染色(第6章第1节)、 邻点强可区别正常全染色(第6章第2节)、 邻和可区别正常边染色(第6章第3节)、 邻和可区别正常全染色(第6章第4节)、邻点可区别无圈边染色(第6章第5节)、 可区别的未必正常的染色(第6章第6节给出了分类). 书中介绍的都是可区别染色方面的重要成果或者作者非常感兴趣的素材. 许多结论的证明过程融入了作者的理解与体会。书中的许多结论都是很新的。
更多好书详见奇趣科学馆
《有趣的科学》（平装全9册，DK*经典*热销的少儿科普丛书，荣获中国童书金奖，新闻出版总署向青少年推荐的百种优秀图书）
《DK科普典藏·礼品套装》(星空 海洋 人体 恐龙全4册)
《有趣的透视立体书 机械篇（全8册）》直观的机械透视感，通透的整体构造展现，每个分页即剖析一个独立的部件，更添加AR互动技术，手机平板等安卓系统就能展现3D立体的虚拟现实效果
《中国古老文化寻踪(全七册)》 用影像探寻文化形态，以文字揭示内在价值，抢救中国传统文化的“活的基因”
《檀岛花事：夏威夷植物日记》（签名本）（全三册）（附精美书签 植物旅行示意图）一套属于你的**。
《征程 从鱼到人的生命之旅》（中英对照）英国自然杂志倾力推荐图书，带你探索中国的“侏罗纪公园”！
《硅谷启示录》惊世狂潮 怦然心动（全2册）
《爆笑科学漫画》物理探秘 化学妙想 环保超人(中英文双语版)（著名漫画家——缪印堂，诺贝尔物理学奖得主——阿诺 彭齐亚斯，鼎力推介）
《轻松自降三高》（套装共3册）全图解、超简单、特实用——让高血压、高血糖、高胆固醇刷刷刷地降下来！
《生态文明决策者必读丛书--生态农场纪实》
《创新的启示——关于百年科技创新的若干思考》（荣膺第九届文津图书奖）
《3D打印 打印未来》
【目录】
目录
第1章点可区别正常边染色
1.1 基本概念及结论
1.2 路和圈的点可区别正常边染色
1.3 n–方体的点可区别正常边色数的渐近性态
1.4 三个引理
1.5 一个上界
1.6 另一个上界
1.7 2–正则图的点可区别正常边色数的一个上界
1.8 **度为2的图的点可区别正常边染色
1.9 进一步阅读建议
第2章邻点可区别正常边染色
2.1 基础理论
2.2 与全染色的关系
2.3 单圈图的邻点可区别正常边色数
2.4 AVDPEC 猜想对于**度为3 的无孤立边的图成立
2.5 二部图的邻点可区别正常边染色
2.6 一般图的邻点可区别正常边色数
2.7 一个上界
2.8 2–退化图的邻点可区别正常边染色
2.9 进一步阅读建议
第3章点可区别全染色
3.1 一个猜想与一个上界
3.2 圈和路的点可区别全染色
图的可区别染色引论
3.3 子母图点可区别全色数之间的关系
3.4 n–方体的点可区别全色数的渐近变化状态
3.5 mK4 的点可区别全染色
3.6 均匀点可区别全染色
3.7 进一步阅读建议
第4章邻点可区别全染色
4.1 基础理论及AVDTC 猜想
4.2 关于**度为3的图的邻点可区别全染色
4.3 一个上界
4.4 完全等多部图的邻点可区别全色数
4.5 广义Halin 图的邻点可区别全染色
4.6 外平面图的邻点可区别全染色
4.7 单圈图的邻点可区别全染色
4.8 进一步阅读建议
第5章D(d)–点可区别边(全)染色
5.1 D(d)–点可区别边染色
5.2 圈的D(d)–点可区别边染色
5.3 一个猜想的反例
5.4 D(d)–点可区别全染色基础
5.5 圈的D(d)–点可区别全染色
5.6 D(d)–VDTC 猜想的反例
第6章其他可区别染色简介
6.1 完全二部图K1; n; K2; n 和K3; n 的点强可区别全染色
6.2 树的邻点强可区别全染色
6.3 邻和可区别边染色
6.4 邻和可区别全染色
6.5 邻点可区别无圈边染色简介
6.6 可区别的未必正常染色的分类
......
【免费在线读】
前言
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 月于西北师范大学
