图 K_n—E(kP_s∪rP_t)的色唯一性

CHROMATIC UNIQUENESS OF K_n-E(kp_s∪rP_t)

本文仅考虑有限、无向、无环的简单图.P(G,λ)表示图 G 的色多项式.如果从P(H,λ)=P(G,λ)可以推出图 H 和 G 同构,则称 G 是色唯一的.设 G 是一个顶点数不超过 n 的图,用 K_n—E(G)表示从完全图 K_n 中删去一个和G 同构的子图的所有边而得到的图.关于 K_n—E(G)型图中的色唯一图的研究已有不少结果,参见[1—5].

Let K_n—E(G) denote the graph obtained from K_n by deleting all the edges ofa subgraph isomorphic to G.In this paper,the concept of irreducible path is intro-duced and K_n—E(kP_s∪rP_t)are shown to be chromatically unique if s≠4,t≠4,and P_s and P_t are irreducible paths.