对具有大围长可平面图强边色数的研究

发布时间：2023-11-24 17:39

　　对图G的所有边进行染色,如果染同种颜色的边构成的集合均在G中形成一个诱导匹配,那么就称该染色方式为图G的强边染色。换言之,如果图G的任意一个长度为3的路径都具有3种不同的颜色,则这种染色称为强边染色。在图G的所有强边染色中所需的最少颜色数称为图G的强边色数,记作χs’(G)。强边染色问题是图论研究的内容之一,在计算机科学及无线通讯网络等领域都有广泛的应用。由于确定图的强边色数是比较困难的,目前大多数的研究都集中了一些特殊图类上。本文首先综述了前人在此方面的研究成果,主要研究了odd图的结构和性质,通过运用odd图研究了平面图的强边染色问题。本文主要结果是：如果平面图G的围长至少为10A(G)+26,则它的强边色数小于等于2Δ(G)-1。

【文章页数】：25 页

【学位级别】：硕士

【文章目录】：
中文摘要
英文摘要
第一章 引言
第二章 基本概念及事实
    §2.1 证明图的强边色数的一些思想
    §2.2 一些已知的结果
第三章 ODD图的结构和性质
第四章 定理的证明
参考文献
致谢



本文编号：3866280