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

通过比较两个图的色多项式的系数(本文使用了五独立集数)、顶点集、边集、三角形和四圈的个数,证明了K(2,2,6)是色唯一图,从而部分地回答了文[5],[7]中遗留的一个问题,并得到图K(n,n,n 4)(n=2或n 4)是色唯一的.     

关于二部图K(m,n)-2的色唯一性

设Ｋ（ｍ，ｎ）－２表示从完全二部图Ｋ（ｍ，ｎ）中删去任意２条边所得之图．本文证明了：１．若ｎ≥ｍ≥３，且ｎ＋ｍ＞(（ｎ－ｍ）^２＋８)^1/2＋１/２（ｎ－ｍ）^２＋４，则Ｋ（ｍ，ｎ）－２是色唯一图；２．当ｍ≥３时，Ｋ（ｍ，ｍ）－２，Ｋ（ｍ，ｍ＋１）－２和Ｋ（ｍ，ｍ＋２）－２均是色唯一图．     

关于完全三部图K(m,n,r)的色唯一性

本文研究完全三部图K(m,n,r)的色唯一性问题，通过比较两个色等价图的色划分数的方法，得出两个关于K(m,n,r)为色唯一图的一般形式数值条件，基本上解决了K(m,n,r)为色唯一图的判定问题．     

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

通过对图的特征子图个数的比较,给出了图K(n-k,n,n)色唯一性的数值条件.     

完全t部图 K(n1,n2,…,nt)的色唯一性

本文使用比较两个色等价图的色划分数的方法,得出了完全t部图的色等价图类仍为完全t部图的一般形式数值条件,进一步得出了K(n1,n2,n3)和K(n1,n2,n3,n4)为色唯一图的一般形式数值条件.     

关于两类特殊图的色多项式唯一性

本文用全新的方法证明了两类图的色多项式唯一性,推广了Beatrice Loe-rine关于广义θ-图的色多项式唯一性的结论。     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

圈和Dn图的补图的色唯一性

圈和Ｄｎ图的补图的色唯一性王守中刘儒英（青海师范大学数学系，西宁８１０００８）关键词图，色多项式，色唯一性．分类号ＡＭＳ（１９９１）０５Ｃ／ＣＣＬＯ１５７．５用Ｐｎ和Ｃｎ表示有ｎ个顶点的路和圈．用Ｄｎ表示把Ｋ３的一个顶点与Ｐｎ－２的一个一度顶点重迭后...     

关于K4同胚图色唯一性的几个新结果

本文证得:如果i,j,k,l,m,n中有四个数相等,而另外二个数不小于此数,则K_4(i,j,k,l,m,n)是色唯一的.此外,我们还得到了另外两族具有色唯一性的K_4同胚图.     

CLASSIFICATION OF COMPLETE 5-PARTITE GRAPHS AND CHROMATICITY OF 5-PARTITE GRAPHSWITH 5n VERTICES

For a graph G,P(G,λ)denotes the chromatic polynomial of G. Two graphs G and H are said to be chromatically equivalent,denoted by G-H,if P(G,λ)=p(H,λ). Let[G]= {H|H-G}. If [G]={G},then G is said to be chromatically unique. For a complete 5-partite graph G with 5n vertices, define θ(G)=(a(G,6)-2^n 1-2^n-1 5)/2n-2,where a(G,6) denotes the number of 6-independent partitions of G. In this paper, the authors show that θ(G)≥0 and determine all graphs with θ(G)= 0, 1, 2, 5/2, 7/2, 4, 17/4. By using these results the chromaticity of 5-partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is investigated,where S is a set of edges of G. Many new chromatically unique 5-partite graphs are obtained.     

6n+5阶的6部图的色性

得到了几类色唯一的6n 5阶的6部图.     

Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets

An $(m,n)$-colored-mixed graph $G=(V,A_1,A_2,\cdots ,A_m,E_1,E_2,\cdots ,E_n)$ is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an $(m,n)$-colored-mixed graph G to another $(m,n)$-colored-mixed graph H is a morphism $\phi :V(G)\to V(H)$ such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An $(m,n)$-colored-mixed graph T is said to be $P_g^{(m,n)}$-universal if every graph in $P_g^{(m,n)}$ (the planar $(m,n)$-colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar $P_g^{(m,n)}$-universal graphs do not exist for $2m+n\ge 3$ (and any value of g) and find a minimal (in the number vertices) planar $P_g^{(m,n)}$-universal graphs in the other cases.     

Estimates of coefficients of chromatic polynomials and numbers of cliques of (c,n,m)‐graphs

This paper is mainly concerned with classes of simple graphs with exactly c connected components, n vertices and m edges, for fixed c,n,m ∈ ?. We find an optimal lower bound for the ith coefficient of the chromatic polynomial of a graph in such a class and also an optimal upper bound for the number of j‐cliques contained in such a graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 81–94, 2003     

两类图的伴随多项式

本文推广已有图D_n,F_n到两类新图D_n~i,F_n~i(i≥4),并运用与色和有关的代数函数—伴随函数得到它们的伴随多项式并讨论了当i=4时的不可约性.     

Chromatic Uniqueness of K4-Homeomorphs with Girth 8

In this paper,we determine all graphs of K4-homeomorphs of girth 8 which are chromatically unique.