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

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

图的色等价与色惟一性是用代数方法研究图论中着色问题一个有着重要意义的研究方法.关于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.