摘要
本文提出广义树、树序列等概念．树、完全图、ｑ－树都是广义树的特例．由于广义树的色多项式容易求得，利用删边－粘点公式可以求一般图的色多项式．广义树的点色数等于它包含的最大点团所含点数，因此利用广义树求一般图的点色数也是一种可行的算法．本文得出广义树的充要条件是不含圈点导出子图Ｃｋ（ｋ≥４），图Ｇ是树序列｛１，ｐ，１，…，１，ｑ｝的广义树的充要条件是Ｇ的色多项式为λ（λ－１）ｐ（λ－２）…
In this Paper we intnduce the nation of generalized trees. Because the chromatic polgnomial of a generalized trees can be easily found .we can write the chromatic polynomial of a general graph by use of the deleting -edgar-contracting-venices formula. The chromatic number of a generalized trees is exactly equal to the vertex number of the maximum clique contained in the generalics trees. So it i. POssible to find the chromatic number of a general graph by use of generalics trees. The necessary aam sutficient condition for a graph to be a gereralized tree given in the present paper is that the graph has no vertex subgraph ck(k≥4) whose venices are in a cycle. We also point out that a graph G is a generalized tree of tree sequence {1,p,1,..', 1,q} if f Ghas a cbromatic polynomial p(G,λ) =λ(λ-1 )'(λ-2)… (λ-r-1) (λ-r-2)'
出处
《新疆大学学报（自然科学版）》
CAS
1995年第1期13-16,共4页
Journal of Xinjiang University(Natural Science Edition)
关键词
广义树
色多项式
色数
generalized trees chromatic polynomial chromatic number
