一类K_4同胚图的色唯一性(英文)

On chromatic uniqueness of K_4-homeomorphs

图的色多项理论是为了研究著名的四色问题建立的一整套理论.虽然色多项式理论未能最终解决四色问题,但其本身涉及到了许多深刻的结果,目前是代数图论的重要研究分支之一.已经知道两个不同构的图可以有相同的色多项式,自然的问题是:在什么条件下两个图的色多项式相同可以推出两个图同构?这就是色唯一性问题.自S.Kahn从60年代开始考虑K4-同胚图的色唯一性问题,许多数学工作者在这方面了一系列的尝试,获得了一批有意义的结果,如至少有两条路长为1的K4-同胚图;围长超过6的K4-同胚图等的染色分类问题已经彻底解决.但是一般K4-同胚图的染色分类问题远未解决.本篇论文研究了围长为7的K4-同胚图染色分类问题.该文采用自创的按图的围长进行分类的方法,利用图的色多项式的特点,细致地分析、挑选出不同构的图.虽然多项式是用经典代数方法来描述图的特征的有力工具,但是,面对众多复杂的、特征线索很少的问题,单纯用多项式来解决问题仍很困难.因此,我们在解决K4同胚图问题时,采用了前人未用过的对色多项式的指数和系数相结合的分析方法,对围长为7的K4-同胚图进行了研究,给出了此类图不具备染色唯一性的充要条件,完全解决了此类图的染色问题.

A K4-homeomorph is a subdivision of the complete graph K4.Such a homeomorph is denoted by K4(α,β,γ,δ,ε,η) if the six edges of K4 are replaced by the six paths of length α,β,γ,δ,ε,η,respectively.Since S.Kahn proposed the problem of chromaticity of K4-homeomorphs,many mathematicians have been working on this problem and many beautiful results are obtained.For example,the study of the chromaticity of K4-homeomorphs with at least 2 *-paths of length 1 has been fulfilled.So far,the study of the chromaticity of K4-homeomorphs remains an active area of research.However,the further study of the chromaticity of K4-homeomorphs is quite complicated.So,in 2004,the author proposed a new classifying method in which the girth is chosen as the character of a graph.By this method,some new results are obtained.For instance,the study of the chromaticity of K4-homeomorphs which have girth less than 6 has been fulfilled.In this thesis,we fulfill the study of the chromaticity of K4-homeomorphs which have girth 7.By using the way of classifying girth of graph,and considering the characteristic of chromatic polynomial,we find out some graphs with same chromatic polynomials but not isomorphic to each other.Although the chromatic polynomial is a very powerful tool of describing the character of graph,for huge amount of complicate graphs with very few features and clues,it is almost impossible to solve problems of chromaticity of graphs if we use chromatic polynomial simply.So,when study the chromaticity of K4-homeomorphs,we adopt lots of technique to analyze the coefficients and the powers of chromatic polynomials and so fulfilled the study of the chromaticity of K4-homeomorphs which have girth 7.