图的与未必正常全染色相关的参数研究

Vertex distinguishing proper edge coloring and the related conjecture are the reseach topics laid stress on by several famous experts of graph theory. The adjacent vertex distinguishing proper edge coloring and (adjacent) vertex distinguishing proper total coloring and the related conjectures have been proposed by famous scolar Zhang Zhongfu and made great progress in recent thirteen years. Adjacent vertex distinguishing and vertex distinguishing general edge coloring had been proposed by Györi E and Harary F respectively and many relevant results had been gotten.The parameters studied in current project are the minimum numbers of the colors required in various not proper total coloring which are vertex distinguishing. We will use the methods of combinatorial analysis, distributing the color sets in advance, constructing of the matrix and calculating of the probability to determine the parameters of several families of graphs, to probe into the relation between the parameters and the corresponding combinatorial degrees, to find the conditions such that the Vizing-like conjectures holds for these parameters, to inquire into the upper bounds of these parameters for general graphs; to research the condition such that the parameter of subgraph is not exceed the corresponding parameter of supergraph.This research is of the significant meanings in revealing the objective laws governing the optimal total coloring which are not necessarily proper and subjected to some conditions. This project will lay a foundation for the study of not necessarily proper total coloring. This will provide the new problems and reseach thinkings.

点可区别正常边染色及其相关猜想是受到当前国际著名图论专家重视的研究课题。而邻点可区别正常边染色、(邻)点可区别正常全染色及其相关猜想被著名学者张忠辅提出后的这十三年里取得了很大进展。邻点可区别及点可区别的一般边染色已被Györi E 与Harary F分别提出并得到了许多结果。本课题所研究的图的参数为图的点可区别的各种未必正常全染色所需最少颜色数。我们将用组合分析、色集合事先分配、矩阵构造、概率计算等方法对各种图类确定相应的参数值，探讨这些参数与相应染色的组合度之间的关系，以期决定这些参数使得Vizing型猜想成立所满足的条件；探讨对于较一般图而言的这些参数的上界；研究子图的参数不超过母图的相应参数的条件。该项目的研究对揭示满足一定条件的未必正常的最优全染色的规律有重要意义，为进一步探索未必正常染色奠定基础，对图染色理论提供新课题及研究思路。

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年分别独立地提出图的点可区别正常边染色，取得了许多重要的成果。此后，图的可区别染色受到越来越多的学者的关注。本项目申请人曾经于2015年底结题的项目主要针对图的（邻）点可区别正常边染色、（邻）点可区别正常全染色等进行研究。本项目主要针对图的点可区别的未必正常全染色进行研究。我们讨论了Cm∨Cn，Cm∨Wn，Cm∨Fn，ｍC3∨ｎC3，ｍC4∨nC4 ， mC2t∨nC2t(ｔ≥３) ， m个阶为4、7、8、15的圈的不交并， 近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色。探讨了一个部所含顶点的数目为4 ―10的完全二部图的点可区别E-全染色。针对完全三部图（并非全部）的点可区别IE-全染色进行了研究，对其中有些完全三部图的点可区别一般全染色也进行了研究，确定了它们的点可区别IE-全色数，也确定了它们中有些图的点可区别一般全色数。对2K_2V K_1 的冠图、两类完全二部图、三星的一般点可区别全染色（亦即点可区别一般全染色）进行了研究。 结论表明VDITC 猜想、VDVITC 猜想、VDETC 猜想、VDIETC 猜想以及VDGTC 猜想对所涉及的图成立。关于某些顶点对被非多重色集合所区别的未必正常染色进行了综述，其中就包括本项目的部分研究成果。本项目所得到的成果丰富和发展了图的可区别染色理论，对可区别染色理论的进一步研究具有一定的参考意义。