【作者】 王东霞；

【导师】 赵连昌；

【作者基本信息】 大连海事大学 ， 应用数学， 2003， 硕士

【摘要】 近二十年来，在理论与实际问题的推动下，由于许多图论学者的努力，图的色性的研究取得很大进展，这一问题的研究是图论的一个活跃课题。 所谓图族的色性就是该图族的色唯一与色等价性。设P（G,λ）表示图G的色多项式。如果P（H,λ）=P（G,λ），那么H和G就称为色等价，如果P（H,λ）=P（G,λ），则H和G同构，那么G就称为色唯一的。图的围长表示图的最短圈的长度。 C.Y.Chao和L.C.Zhao研究了n点n+2边图族的色性，他们首次给出了F中图的色多项式，按照图的色多项式把n点n+2边图族F分成三个子族F₁、F₂、F₃，得到了关于F色性的许多重要结论。K.L.Teo和K.M.Koh研究了2-连通n点n+2边且包含长度为4的圈或两个三角形的图族，给出了色等价与色唯一的分类。X.E.Chen和K.Z.Ouyang研究了2-连通n点n+2边围长为5且不与K₄同胚的图族，给出了色等价与色唯一的分类。 本文给出了2-连通n点n+2边围长为6且不与K₄同胚的图族W₁和2-连通n点n+2边围长为7且不与K₄同胚的图族W₂的色性。 通过详细分析，我们把图族W₁和W₂分成几个子族，按照Chao和Zhao的公式，比较了子族之间色多项式的系数，给出了色等价和色唯一的图族。更多还原

【Abstract】 In the last twenty years the theory of the chromaticity of graphs has been greatly developed through the inspiration of many specialists in graph theory, motivated by theoretical and actual problems. The topic of the chromaticity of graphs is a very active one in graph theory. ’The problem of the chromaticity of a family F of graphs means the determining of the chromatically equivalent classes and the chromatically unique classes of F. Let P(G, A) denote the chromatic polynomial of a graph G. Two graphs H and G arechromatically equivalent if P(H, 2) = P(G, A.). A graph G is chromatically unique ifP(H, X) = P(G, A) implies that H isomorphic to G. The girth of a graph is the length ofthe shortest cycle.C.Y.Chao and L.C.Zhao studied the chromaticity of the family F of graphs with n+2 edges and n vertices. They first computed the chromatic polynomials of graphs in F and then divided this family into three subfamilies, F\, F2 and /^according to their chromatic polynomials and finally proved many results. K.L.Teo and K.M.Koh studied the chromaticity of the family of 2-connected (n, n+2)-graphs which contain a 4-cycle or two triangles. X.E.Chen and K.Z.Ouyang studied the chromaticity of the family of 2-connected (n, ?2)-graphs which have girth 5 and are not homeomorphic to K4.This thesis studies the chromaticity of the family W\ of 2-connected (n, n+2)-graphs which have girth 6 and are not homeomorphic to K4, and the family W2 of 2-connected (n, n+2)-graphs which have girth 7 and are not homeomorphic to K4.We divided W1 and Wi respectively into some subfamilies by exhaustion. According to the formula of Chao and Zhao, in this thesis by comparing the coefficients of chromatic polynomials of the subfamilies we determine all equivalent classes and obtain some unique graphs in W1 and Wi..更多还原