论文部分内容阅读
图论是一门与现实生活密切联系的学科,而图的着色问题是图论中最古老的也是最典型的问题之一。最初人们只是对图的一个元素研究它的着色问题,即顶点着色或边着色;然而现实生活中很多问题是比较复杂的,用简单的边着色和顶点着色很难准确的描述图的特征,于是,人们引入了图的全着色的概念。
设G是一无环图,k是整数,f是V(G)UE(G)到集合C={1,2,…,k}的映射,若满足以下条件:
(1)对于任意的,uv,vw∈E(G),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,并称数min{k|存在G的k-TC}为G的全色数,简记为Xt(G)。
本文,在第一章,首先简单的回顾了图论的悠久的历史,然后描述了图的着色理论的发展,接着展现了图的全着色理论研究的现状;在第二章,我们给出了本文所要用到的基本概念,以及全着色的基本性质,第三章,我们主要研究了树与路的联图的全着色,并且给出相应的结果。最后,我们对本文进行了总结,并且对所研究问题进行了展望。