樹與路的聯(lián)圖的全色數(shù).pdf

1、圖論是一門與現(xiàn)實生活密切聯(lián)系的學科，而圖的著色問題是圖論中最古老的也是最典型的問題之一。最初人們只是對圖的一個元素研究它的著色問題，即頂點著色或邊著色；然而現(xiàn)實生活中很多問題是比較復雜的，用簡單的邊著色和頂點著色很難準確的描述圖的特征，于是，人們引入了圖的全著色的概念。
　　 設G是一無環(huán)圖，k是整數(shù)，f是V（G）UE（G）到集合C={1，2，…，k}的映射，若滿足以下條件：
　　 （1）對于任意的，uv，vw∈E（G）

2、，u≠w都有，f（uv）≠，f（vw）。
　　 （2）對于任意的uv∈E（G），都有f（u）≠f（v），f（u）≠，f（uv），f（v）≠f（uv）。
　　 則稱f是G的全著色，簡記作為k-TC，并稱數(shù)min{k｜存在G的k-TC}為G的全色數(shù)，簡記為Xt（G）。
　　 本文，在第一章，首先簡單的回顧了圖論的悠久的歷史，然后描述了圖的著色理論的發(fā)展，接著展現(xiàn)了圖的全著色理論研究的現(xiàn)狀；在第二章，我們給出了本文所要