Pkn和T(k1,k2,…,kn)的色多项式

本文研究了图Pkn和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及P2n仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

完全t部图K(n-k,n-2,n,…,n)的色唯一性

文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。     

关于完全三部图色唯一性的判定

G是简单图,用P(G,λ)表示图的色多项式.若对任意简单图H当P(H,λ)=P(G,λ)时,都有HG,则称G是色唯一图.Liu R.,Zhao H. X.和Ye C.已经证明:当n和k为整数且满足n≥k 2≥4,完全三部图K(n-k,n,n)是色唯一的;当n和k满足n≥2k≥4时,完全三部图K(n-k,n-1,n)是色唯一的.在本文中,证明了当k是奇数且n≥k2/4 15/4≥6,或k是偶数且n≥k2/4 4≥5时,完全三部图K(n-k,n-2,n)是色唯一的;当k是奇数且n≥k2/4 19/4≥7,或k是偶数且n≥k2/4 5≥9时,K(n-k,n-3,n)是色唯一的.     

三部图K(m,n,r)-A(|A|=2)的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,令K(m,n,r)表示完全三部图.证明了1)当3≤m≤n≤r时,令s=1/√6√(n-m)2 (r-n)2 (r-m)2 12,若m n r＞2√3s 3s2,则K(m,n,r)-A(|A|=2)是色唯一图;2)当m≥4时,K(m,m,m)-A,K(m,m,m 1)-A,K(m,m 1,m 1)-A,(|A|=2)都是色唯一图;3)设n,k为非负整数,则当n＞k2 2√k2 6 k 2时,K(n-k,n,n)-A;当n＞k2 2√k2 6-k/3 2时,K(n,n,n k)-A;当n＞2√3k2 6 k2 2时,K(n-k,n,n k)-A(|A|=2)均为色唯一图.     

完全t部图K（n-k,n,…,n）的色唯一性

设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M, Teo K L. The search for chromatically unique graphs. Graphs and Combinatorics, 1999,6: 259-285]中提出的猜想(若n≥k 2,则完全三部图K(n-k,n,n)是色唯一图);推广了文献[Liu Ru-yin, Zhao Hai-xing, Ye Cheng-fu. A complete solution to a conjecture on chromatic unique of complete tripartite graphs. Discrete Mathematics, 2004, 289: 175-179]中的结果(若n≥k 2≥4,则K(n-k,n,n)是色唯一图;若n≥2k≥4,则K(n-k,n-1,n)是色唯一图);证明了若n≥k 2≥4,则K(n-k,n,...,n)是色唯一图,若n≥k 2≥4,则K(n-k,n-1,n,...,n)是色唯一图.     

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

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

完全三部图K(n-4,n,n)的色唯一性

设G是简单图,用P（G,λ）表示图G的色多项式．若对任意图H使P（H,λ）＝P（G,λ）,都有H与G同构,则称G是色唯一图．用K（m,n,r）表示完全三部图,证明了当K＝4时,如下猜想[1]成立：对非负整数n,k,当n≥k＋2时,K（n－k,n,n）是色唯一图．即当n≥6时,K（n－4,n,n）是色唯一图．     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

一类完全三部图K(m,n,r)的色唯一性的判定

设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图。令K(m,n,r)表示完全三部图,证明了(1)设m≤n≤r,0≤r-m≤4,若m≥2,则除去K(2,2,6)、K(2,3,6)、K(3,3,7)、K(3,4,7)外,K(m,n,r)是色唯一图。(2)若n≥4,0≤k≤2,则K(n-k,n,n k)是色唯一图。     

一类色唯一的K_1-同胚图

令K4(i,j,k,l,m,n)表示图G的色多项式,如果P(G)=P(H),称G和H色等价;如果对任意图H,当P(H=P(G))时,都有H和G同构,称G是色唯一的.令K4(i,j,k,l,m,n)表示两两三度点间的路长分别为i,j,k,l,m,n的K4-同胚图.作者对集合{i,j,k,l,m,n}由3个不同值组成,且等于每个值的路都恰有2条的K4-同胚图的着色进行了研究,得到了1类色唯一的K4-同胚图.     

一类图的色性

证明色多项式的根全为非负整数的4色图含有K_4子图,并讨论了此类图的色性。     

几种图的对策着色和对策色数

介绍了一种新的色对策和对策色数,比较了2种色对策的差异.对几种特殊的图形的色对策数进行了讨论,运用顶点标号方法,给出获胜策略.     

一类K4同胚图的色唯一性

本文主要讨论了当J{i,j,k,l,m,n}l的个数小于等于4时,k4(i,j,k,l,m,n)的色性.     

图上的对策着色和对策着色数

图G的对策色数Ⅱχg(G)是由图的点色数χg(G)拓展而来的.本文对几类特殊的图进行了讨论,分别给出了图Qn,Gn以及与圈有关图的对策色数Ⅱ,并给出了选手Alice相应获胜的对策.     

路圈并补图色唯一的新结果

文献［１,２］讨论了路圈及其并的补图的色性,本文用新方法证明了图ＰｋＵ（ＵＣ(ｕｉ)）的补图在ｋ＝３．５或ｋ≠４为偶数的条件下色唯一,改进了［１,２］的结果。     

外平面图的松弛竞赛色数

主要研究外平面图的松驰竞赛色数。如果缺陷度d =2 ,3 ,4 ,k =7-d ,我们能够分别给Alice一个策略 ,使得对 (k ,d) 松弛染色竞赛Alice能赢。     

超图的分数着色研究

图的分数着色问题是分数图论中的一个重要研究课题之一，超图作为图的推广在实际中有着广阔的应用．本文将一般图中分数着色的几个重要结论推广到超图，并证明其正确性。     

n个图的逻辑积的色数和边色数

证明了图的逻辑积的色数公式ｘ（Ｇ１∧Ｇ２∧…∧Ｇｎ）≤ｍｉｎ｛ｘ（Ｇ１），ｘ（Ｇ２），…，ｘ（Ｇｎ）｝，边色数有并作如下猜想：ｘ（Ｇ１∧Ｇ２∧…∧Ｇｎ）＝ｍｉｎ｛ｘ（Ｇ１），ｘ（Ｇ２），…，ｘ（Ｇｎ）｝．     

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

线图的星色数

G是简单图,LG表示G的线图,对LG的星色数进行了讨论,并得出了X^*(LG)=X(LG)的两个充分条件,以及一类特殊图线图的星色数的值。