一类K_4同胚图的色唯一性（英文）

• 作者: 彭燕玲
• 来源期刊: 南京大学学报：自然科学版
• 学科: 数学
• 关键词: 色多项式 色唯一 K4同胚图
• 年，卷（期）: 2012,（1）
• 页码范围: 40-47
• 分类号: O157.5
• 语种: 中文

摘要

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