本文提出广义树、树序列等概念.树、完全图、q-树都是广义树的特例.由于广义树的色多项式容易求得,利用删边-粘点公式可以求一般图的色多项式.广义树的点色数等于它包含的最大点团所含点数,因此利用广义树求一般图的点色数也是一种可行的算法.本文得出广义树的充要条件是不含圈点导出子图Ck(k≥4),图G是树序列{1,p,1,…,1,q}的广义树的充要条件是G的色多项式为λ(λ-1)p(λ-2)…(λ-r-1)(λ-r-2)q
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)'
0
浏览量
52
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621
