一类2-连通(n,n+2)-图的色等价与色惟一性  

Chromatic equivalence and uniqueness of certain (n,n+2)-graphs

作　　者：王东霞[1] 赵连昌[1] 邓秋红[1] 

机构地区：[1]大连海事大学数理系,辽宁大连116026

出　　处：《大连海事大学学报》2004年第2期96-99,共4页Journal of Dalian Maritime University

基　　金：国家自然科学基金资助项目(19871007).

摘　　要：图的色等价与色惟一性是用代数方法研究图论中着色问题一个有着重要意义的研究方法.关于2 连通(n,n+2)有4长圈或两个三角形,或围长为5且不与K4同胚的图族的色等价与色惟一问题已有结果.本文基于图的同胚分类和色多项式系数的比较,给出2 连通(n,n+2)围长为6又不与K4同胚的图族的色等价子族和色惟一子族.The length of a shortest cycle of a graph G is called the girth of G. Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. A graph G is said to be chromatically unique if for any graph H which is chromatically equivalent to G implies that H isomorphic to G. Finding chromatically unique graphs is an interesting problem in graph theory. The chromaticity of 2-connected (n,n+2) graphs which contain a 4-cycle or two triangles, or which have girth 5 and are not homeomorphic to K_4　had been discussed. In this paper, based on the homeomorphic classification and comparing the coefficients of the chromatic polynomials of the family of 2-connected (n,n+2) graphs that have girth 6 and are not homeomorphic to K_4, the chromatically equivalent subfamilies and the chromatically unique subfamilies of the family are presented.

关 键 词：2-连通图 色等价 色惟一性 

分 类 号：O157.5[理学—数学]