广义树的结构和色性

作     者：龚和林 

作者单位：上海师范大学 

学位级别：硕士

导师姓名：唐明元

授予年度：2005年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：n-临界图 广义树 色多项式 色等价 色唯一 

摘      要：本文研究了广义树的色多项式和色唯一性,广义树的色性研究是继q-树、广义θ-图、广义轮图θ的色性研究之后的新课题。弦图指图中任何长度大于3的圈都含弦的图,弦图G的色多项式为P(G,λ) = λ(λ-1) ···(λ-m),其中,r + ···+ r = |v(G)|,r ∈Z(i = 1,2,···,m),1974 年,K. Brown猜想具有上述形式色多项式的图均为弦图。1975年,R.C. Read从K6的一边剖分一个顶点构造图H,则P(H,λ) = λ(λ-1)(λ-2)(λ-3)(λ-4),由于H含4个无弦四圈,H不是弦图,从而否定了K. Brown的猜想,即弦图不能由其色多项式决定。广义树即连通弦图,本文利用色分类、临界图、色等价图的相关性质给出几类由色多项式决定的广义树及其构造,并证明一系列与广义树色等价的非广义树存在,利用上述结果,本文获得并证明了广义树是色唯一的的一个充要条件,从而也从侧面完整解答了K. Brown的猜想。 全文共分五章。第一章,前言部分介绍图的色性研究的理论背景和本文作者的主要工作;第二章,概述着色理论、色多项式、色等价与色唯一的相关理论;第三章,介绍和讨论广义树和非广义树特征,并给出几类由色多项式决定的广义树;第四章,分析和研究广义树色多项式,由此证明广义树G是色唯一的,当且仅当其色多项式P(G,λ)没有重根或只含一个重根,且重数为2;第五章,结论。