詹福琴,乔友付,罗美金

(河池学院 数学系,广西 宜州 546300)

0 引 言

本文仅考虑有限、无向的简单图[1].p(G,λ)表示图 G的色多项式.对于图 G和 H,如果 P(G,x)=P(H,x),称 G和 H色等价,简记为 H～G.[G]表示图 G的色等价图类.称图 G是色唯一的,如果[G]={G}.文献 [2]定义了具有 p个顶点的图 G的伴随多项式为其中 bi(G)表示 G恰有 p-i个分支的理想子图的个数.如果 h(G,x)=h(H,x),称两个图 G和 H是伴随等价的,简记为 H～hG.用 [G]h表示图 G的伴随等价图类.称图 G是色唯一的,如果 [G]h={G}.文献 [3]证明了图 G色唯一当且仅当其补图伴随唯一;G～ H当且仅当文献 [3-7]利用伴随多项式的代数性质研究了许多色唯一图,但对大量非色唯一图的色等价刻画有待研究.本文完整刻画了一类稠密图的色性.

1 预备知识

设 G是一个图,V(G),E(G),p(G),q(G)和分别表示图 G的顶点集,边集,顶点数,边数和补图.G∪ H表示 G和 H不相交的并图,kG表示 k个 G不相交的并图.NG(v)表示图 G中与顶点 v相邻的点集[8].U(G)表示图 G的伴随多项式 h(G,x)的最小实数根.∂(h(G,x))表示伴随多项式h(G,x)的次数.为方便叙述,令 h(G)=h(G,x),h(a,b,c)=h(T(a,b,c),x),h(a,b,c,d,e)=h(T(a,b,c,d,e),x);U(a,b,c),U(a,b,c,d,e)分别表示 h(a,b,c)和 h(a,b,c,d,e)的最小实数根.

Pn和 Cn分别表示 n个顶点的路和圈.Dn表示把 K3的1个顶点和 Pn-2的1个 1度点重叠后得到的图.Fn表示把 K3的 1个顶点与 Dn-2的 1度点重叠后得到的图.

对具有 n个顶点且度序列为(1,1,1,2,2,...,2,3)的树称为 T-形树,记为 Tn(l1,l2,l3),或简记为T(l1,l2,l3).树 T(a,b,c,d,e)表示从 Pc+1的 2个 1度点分别引出两条长为 a,b和 c,d的路得到的图.

Cm(Pn)表示 Cm的 1个顶点和 Pn的 1个 1度点重叠后得到的图.特别地,把 Cm(P2)记作 An.C3(Pm,Pn)表示 K3的 2个顶点分别与路 Pm和 Pn的 1个 1度点重叠后得到的图.C3(T(a,b,c))表示 K3的 1个顶点和 T(a,b,c)的长为 a的路的 1度点重叠后得到的图.特别地,把 C3(T(a,1,1))记作 Bn.

文中……