几类图的色多项式问题

定义１设图Ｇ为含有 ｐ个顶点的标定图 ,对其进行ｘ———正常染色的方法数是ｘ的一个函数 ,可表示成ｘ的一个多项式 ,称为图Ｇ的色多项式 ,记为ｆ（Ｇ ,ｘ）。引理１给定图Ｇ ,设ｕ、ｖ∈Ｖ（Ｇ） ,ｅ＝（ｕ ,ｖ）∈Ｅ（Ｇ）则ｆ（Ｇ ,ｘ）＝ｆ（Ｇ -ｅ ,ｘ） -ｆ（Ｇｏｅ ,ｘ）引理２设Ｇ是含ｑ条边ｋ个分图的 ｐ阶图 ,则①ｆ（Ｇ ,ｘ）是ｐ次多项式 ;②ｆ（Ｇ ,ｘ）中ｘｐ的系数为１;③ｆ（Ｇ ,ｘ）ｘｐ -１的系数为 - ｑ;④ｆ（Ｇ ,ｘ）中常数项为０;⑤ｆ（Ｇ,ｘ）＝∏ｆ（Ｇｉ,ｘ） ,式中Ｇｉ 是Ｇ的第ｉ个分图 ;⑥ｆ（Ｇ,ｘ）中 ,系…     

完全三部图K（n,n,n＋k）的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）为Ｇ的色多项式。若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图。证明了（１）对任意非负整数ｋ,若ｎ≥ｋ＋ｋ＾２／３,则Ｋ（ｎ,ｎ,ｎ＋ｋ）是色唯;（２）若ｎ≥４,则Ｋ（ｎ,ｎ,ｎ＋４）是色唯一图。     

非标定图的σ－多项式

对标定图Ｇ的σ－多项式σ（Ｇ）有以下基本定理：设Ｇ∨Ｈ是标定图Ｇ与Ｈ的联图，则成立σ（Ｇ∨Ｈ）＝σ（Ｇ）σ（Ｈ）．本文对非标定图的σ－多项式给出了这一定理的相应结果，并据此得到了非标定完全多部图的σ－多项式与色多项式的计算公式．     

完全三部图K(n- k,n,n)的色性

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式;若对任意简单图Ｈ 满足Ｐ（Ｈ,λ） ＝ Ｐ（Ｇ,λ）,都有Ｈ 与Ｇ同构,则称Ｇ是色唯一图;设Ｋ（ｍ ,ｎ,ｒ） 表示完全三部图;本文证明了：（１） 若ｎ ＞ ｋ ＋ ｋ２／３,则图Ｋ（ｎ － ｋ,ｎ,ｎ） 是色唯一的,（２） 若ｎ ≥８,则Ｋ（ｎ － ４,ｎ,ｎ） 是色唯一的;     

二部图K(m,n)-A中的色正规图类

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式。简单图Ｈ称为与Ｇ是色等价的（记作Ｈ￣Ｇ）,如果Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）。简单图类Ｌ称为色正规图类,若对任意Ｈ,Ｇ∈Ｌ使Ｈ￣Ｇ都有Ｈ与Ｇ同构。     

一类图的色唯一性

设Ｐ＿ｍ表示有ｍ个顶点的路。把Ｋ＿３的一个顶点与Ｐ＿（ｎ－２）的一个一度顶点重迭后所得到的图记为Ｄ＿ｎ。本文引入了不可约图的概念，并证明了：如果对任意的ｉ∈｛１，２，…ｒ｝，都有ｎ＿ｉ≥５，并且Ｄ＿ｎ＿ｉ是不可约图，则Ｄ＿ｎ＿１∪Ｄ＿ｎ＿２∪…∪Ｄ＿ｎ＿ｒ的补图是色唯一图。     

一类色等价图的图特征

给出了一个有割点的连通图Ｇ是色唯一的充分必要条件为Ｇ由一个色唯一,顶点可迁图连一尾构成,进而证明了若Ｍ为色唯一,不含分离边的连通图,且Ｐ（Ｇ,λ）＝（λ－１）＾ｋｐ（Ｍ）则Ｇ含一子图同构于Ｍ及Ｋ个桥。     

广义q－轮W（5＋q）和W（7＋q）的色性

设Ｐ（Ｇ，λ）表示图Ｇ的色多项式．图Ｇ称为色唯一的，如果由可得到．一个广义ｑ－轮是Ｃｎ和Ｋｑ的联图．记作Ｗ（ｎ＋ｑ）．证明了Ｗ（５＋ｑ）和Ｗ（７＋ｑ）不是色唯一的．     

广义树的色性

设Ｇｎ 是一棵ｎ 阶的广义树,证明了Ｇｎ 的色多项式Ｐ（Ｇｎ）＝ λ（λ－ １）ｒ１ （λ－ ２）ｒ２…（λ－ｍ ）ｒｍ ,这里,１＋ ｒ１＋ …＋ ｒｍ ＝ ｎ;并且当ｎ＞ １ 时,ｒｉ≥１（ｉ＝ １,２,…,ｍ ）⒀以及存在图Ｇ,使得Ｇ不是一棵广义树,但Ｐ（Ｇ）＝ Ｐ（Ｇｎ＋ ２     

一类图的色等价图类

设G是一个图,P（G,λ）是G的色多项式,用[G]p表示以P（G,λ）为其色多项式的所有图的集合,称为图G的色等价类.刻画了[I^cm]p,其中Im（m≥6）表示路Pm-4的两个端点分别粘接一个^＋P3的2度点后得到的图.G^c表示G的补图.     

满足│a1（G）│=24的图G的结构

让ａ１（Ｇ）表示图Ｇ的色多项式的一次项系数，给出满足条件│ａ１（Ｇ）│＝２４的图Ｇ的结构。     

几类G=（p,p＋1）且R（G）=—2图簇的补图的色性

本文利用图Ｇ的伴随多项式的最小根的性质,讨论了几类ｎ个点ｎ＋１条边且Ｒ（Ｇ）＝－２不可约图的补图的色性。     

不含K1＋P3和C4作为导出子图的图的色数

Erodos证明了对于一个图G ,χ（G）-ω（G）可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1＋ P3和C4作为导出子图的图,那么当α（G ）≥3时,χ（G ）＝ω（G ）;当α（G ）＝2时,χ（G ）n ≤2ω（G ）。     

图UnUK4-的色等价刻画

h（G，x）表示图G的伴随多项式，它从图G的补图出发研究色惟一和色等价．若P（G，λ）：P（H，λ），称G和H色等价，一个图被称为是色惟一的，如P（G，λ）=P（H，λ）意味着G≈H．若h（G，x）：h（H，x），称G和H伴随等价；G和H色等价当且仅当G^-和H^-伴随等价；G色惟一当且仅当G^-伴随惟一．Un表示从路Pn-4的每个1度点分别引出两个悬挂边所得到的具有两个3度点4个1度点的树．K4^-表示从K4中删去一条边得到的图．应用伴随多项式理论研究了图（UnUK4^-）^-的伴随多项式系数和根的性质，以此为基础刻画了图（UnUK4^-）^-的色等价图类。     

图染色数的一个结果

图Ｇ的染色数Ｘ（Ｇ）是使得Ｇ中任何相邻两点均染不同色的最小颜色数。文中证明了，如果ω（Ｇ）≥６，△（Ｇ）＝ω（Ｇ）＋１，ㄧＶ（Ｇ）ㄧ≤２ω（Ｇ）＋１，则Ｘ（Ｇ）＝ω（Ｇ），给出了两个图Ｇ０，Ｇ１，使得ㄧＶ（Ｇ０）ㄧ＝１４，ω（Ｇ０）＝６，△（Ｇ０）＝７，Ｘ（Ｇ０）＝７；ㄧＶ（Ｇ１）ㄧ＝１１，ω（Ｇ１）＝５，△（Ｇ１）＝６，Ｘ（Ｇ１）＝６。     

两类新的色唯一图簇

讨论了形如（Ｄｍｌ∪…∪Ｄｍｋ）∪（Ｐｎｌ∪…∪Ｐｎｌ）以及（Ｄｍｌ∪…∪Ｄｍｋ）∪（Ｃｎｌ∪…∪Ｃｎｔ）的两类图的补图的色性，并证明了，在一定的限制条件下，它们是色唯一图．     

两种图的色类

讨论了两种图的色类．第一种图是围长为３的２－连通（ｎ，ｎ＋２）－图；第二种图是０（１，ｂ，ｃ、ｄ）．     

图染色数的一个结果

图Ｇ的染色数Ｘ（Ｇ）是使得Ｇ中任何相邻两点均染不同色的最小颜色数．文中证明了：如果ω（Ｇ）≥６，△（Ｇ）＝ω（Ｇ）＋１，｜Ｖ（Ｇ）｜≤２ω（Ｇ）＋１，则Ｘ（Ｇ）＝ω（Ｇ），给出了两个图Ｇ０、Ｇ１，使得｜Ｖ（Ｇ０）｜＝１４，ω（Ｇ０）＝６，△（Ｇ０）＝７，Ｘ（Ｇ０）＝７；｜Ｖ（Ｇ１）｜＝１１，ω（Ｇ１）＝５，△（Ｇ１）＝６，Ｘ（Ｇ１）＝６．     

图Kn—E（kPs∪rK3）的色唯一性

利用不可约路的概念，证明了当Ｐｓ是不可约的路时，Ｋｎ－Ｅ（ｋＰｓ∪ｒＫ３）是色唯一的图，其中设Ｋｎ－Ｅ（Ｇ）表示从完全图Ｋｎ中删去一个和Ｇ同构的子图的所有边而得到的图，ｓ≠４，且ｋｓ＋３ｒ＝ｎ，ｋ３是有３个顶点的完全图，同时给出了三类新的色等价图簇。     

关于完全三部图K(n-k,n,n+k)的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）的色多项式,若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图,证明了：（１）对任意非负整数ｋ,若ｎ≥２√－３ｋ／３＋ｋ＾２,则Ｋ（ｎ－ｋ,ｎ,ｎ＋ｋ）是色唯一图。（２）若ｎ≥９,则Ｋ（ｎ－３,ｎ,ｎ＋３）是色唯一图。