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