题目：关于图的全色数

1965年，Behzad在其博士论文中提出了如下猜想： 全染色猜想（Tcc）：对任意简单图G，有 _XT（G）≤△（G）+2 显然，_XT（G）≥△（G）+1，围绕这个猜想，人们作了大量的工作，证 明了TCC在一些特殊情况下是成立的，如当△（G）≤5, △（G）≥3/4∣G∣ 时TCC成立。对一般情况尚不知TCC是否成立，另一方面，若TCC 成立，那么图G在什么条件下满足_XT（G）＝△（G）+1？在什么条件 下满足_XT（G）＝△（G）+2？关于上述问题，张忠辅曾给出了如下猜想： 猜想1：如果图G只有一个最大度点，则_XT（G）＝△（G）+1 猜想2：如果图G的最大度点互不相邻，则_XT（G）＝△（G）+1 本文首先讨论了以上三个猜想之间的关系，证明了猜想1和猜想2 都强于TCC，其次证明了猜想1和猜想2在某些条件下是成立的。 另外，本文给出了解决TCC的一个新思路，试图通过对△（G）实 施归纳去证明猜想2.用这个思路去证明猜想2尚需解决一个问题，那 就是，若猜想1对最大度为△的图成立，猜想2对最大度为△的图 是否也成立？若答案是肯定的，我们就可以利用这种思路去证明猜想2， 从而证明TCC成立，最后，本文还考虑了两个图的联图的全色数。