论文部分内容阅读
染色问题是图论研究的经典领域，它源自四色定理的研究，是图论研究中一个很活跃的课题．另外染色问题在组合分析和实际生活中有着广泛的应用，因此各类染色问题被相继提出并加以发展、应用．
图G的一个(正常)k-染色是将k种颜色分配给G的顶点集V(G)，使得相邻两顶点的颜色不同．定义色数为：x(G)=min{k|图G有k-染色)．类似地，图G的一个(正常)k-边染色是将k种颜色分配给G的边集E(G)，使得有公共端点的两边的颜色不同．边色数x’(G)=min{k}图G有k-边染色}．
图的全染色的概念是对点染色和边染色的推广，是对图的所有元素(顶点和边)都进行染色，使得相邻或关联的两元素颜色不同．图的全色数xT(G)=min{k|图G有k-全染色}．全染色是图论染色的一个传统问题，由Vizing(1964)[1]和Behzad(1965)[2，3]各自独立提出的，同时分别给出全染色猜想．
邻点可区别的全染色的概念是图的一正常的全染色且任相邻顶点的色集不同，由张忠辅[4]在全染色的基础上提出的，并同时给出了相应的猜想和两个引理．用xat(G)表示图G的邻点可区别的全色数．
超图是—般图的一个重要推广，超图的染色问题也是图的染色问题的推广．1966年Behzad首次开始超图染色的研究，逐渐地将染色理论引入到超图中来．超图的全染色的概念是图的全染色概念的一个自然推广．王维凡，张克民在[5]中给出了超图全染色的概念，分为弱全染色和强全染色两种．超图H-(V. E)的弱(强)全染色是对超图的所有元素(顶点和超边)都将进行染色，使得顶点是弱(强)染色，边是强边染色，并且任意关联的顶点和超边的颜色不同．超图的弱(强)全色数XWT(H)=min{k超图H有弱k-全染色}(XST(H)=min{k|超图日有强k-全染色})．
图的分数染色的概念是从图染色的分数推广的角度提出的． E．Scheinennan和D．Ullman在[6]中提出了分数染色的概念，并指出确定一个图的分数色数是NP-困难的．用xf(G)表示图G的分数色数．