南京大学学报(自然科学版) ›› 2012, Vol. 48 ›› Issue (1): 40–47.

• • 上一篇    下一篇

 一类K4同胚图的色唯一性

 彭燕玲
  

  • 出版日期:2015-05-20 发布日期:2015-05-20
  • 作者简介: (l.爱达荷大学数学系,美国,爱达荷,83844;
    2.苏州科技学院数学系,苏州,215009)
  • 基金资助:
     The National Natural Science Foundation of China(10671090)

 On chromatic uniqueness of K4-homeomorphs*

 Peng Yan-Ling**
  

  • Online:2015-05-20 Published:2015-05-20
  • About author: (1 .Department of Mathematics,The University of Idaho,Moscow, 83844,USA
    2. Department of Mathematics,Suzhou University of Science and Technologv,Suzhou,215009,China)

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

Abstract:  A K4-homcomorph is a subdivision of the complete graph K4.Such a homcomorph is denoted by K4 (α,β,γ,δ,ε,η)if the six edges of K4 are replaced by the six paths of length a,α,β,γ,δ,ε,η,
respectively. Since S. Kahn proposed the problem of chromaticity of K4-homcomorphs, man mathematicians have been working on this problem and many beautiful results arc obtained. For example
the study of the chromaticity of K4-homcomorphs with at least 2*-paths of length 1 has been fulfilled.So far,the study of the chromaticity of K4-homcomorphs remains an active area of research. However,thc
further study of the chromaticity of K4,-homcomorphs is quite complicated. So,in 2001,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 arc obtained. For instance, the study of the chromaticity of K4- homcomorphs which have girth less than 6 has been fulfilled. In this thesis, we fulfill the study of the chromaticity of
K4,-homcomorphs 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-homcomorphs,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-homcomorphs which have firth 7.

[1]Guo Z Y,Earl G W Jr. Chromaticity of a family of K4-homcomorphs. Discrete Mathematics, 1997,172:53一58.
[2]Liu M. Almost every K4-homcomorph is chro matically unique,Ars Combinatoria, 1987,23: 13一36.
[3]Xu S. Chromaticity of a family of K4-homeo- morphs. Discrete Mathematics,1993,117:293~ 297.
[4]Peng Y L,Liu R Y. Chromaticity of a family of  K4-homcomorphs. Discrete Mathematics, 2002,258:161~177
[5]Peng Y L. Some new results on chromatic uniqueness of K4-homcomorphs.Discrete Mathematics , 2004 , 288:177一183.
[6]Koh K M,Teo K L. The search for chromati cally unique graphs.Graph and Combinatorics 1990,6:259一285.
[7]Xu S. A lemma in studying chromaticity. Ars Combinatoria, 1991,32:315一318.
[8]Chao C Y,Zhao L C. Chromatic polynomials of  a family of graphs. Ars Combinatoria, 1983,15.111~129
[9]Whitehead E U Jr,Zhao L C. Chromatic unique ness and equivalence of K4-homcomorphs. Joui- nal of Graph Theory, 1984,8:355一364.
[10]Ren H Z. On the chromaticity of K,-homeo morphs. Discrete Mathematics,2002,252:247~257
[11]Peng Y L. Chromatic uniqueness of a family of  K4-homcomorphs. Discrete Mathematics, 2008 308:6132-6140.
[12]Peng Y L. A family of chromatically unique K4- homeomorphs. Ars Combinatoria,in press.
[13]Lin W, Lam P C B, Shiu W C. Circular chro- matic numbers of the generalized Myciclskians of cycles. Journal of Nanjing University Math matical Biquarterly,2006,23(2):232一241.


No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!