图的单色连通数

发布时间：2021-02-19 22:15

　　边染色图的研究是图论研究的热点问题之一,边染色图的连通性问题是最近十余年以来其中一个十分活跃的课题。给定图G的一个边染色,如果该染色使得图G的任意两顶点都有一条单色路径相连,那么称该边染色为图G的一个单色连通染色[4]（简记为MC-染色）.图G的单色连通数是指,使得图G有单色连通染色的最大颜色数,符号表示为mc（G）.图的单色连通问题是由Caro&Yuster在2011年提出.近些年来,研究者们对图的单色连通问题做了一系列研究,其中大多是对图的单色连通数的上下界进行刻画.本文主要研究图的单色连通数,以及其极值边染色的特征刻画.对于任意的连通图G的单色连通数都有这样一个直接的下界:mc（G）≥m（G）-n（G）+2[4].同时Caro&Yuster也给出了一些上界,其中包括mc（G）≤m-n+χ（G）.以下是本文的主要结构和研究内容.在第一章中,主要介绍了本论文所涉及的图论基本概念和术语,对图的单色连通数问题的研究背景和研究现状进行详细阐述,并简要叙述了本学位论文的主要结果.在第二章中,主要研究了三色图的单色连通数,并完全解决了相关问题.在第三章中,主要研究了 r-部图的... 

【文章来源】：浙江师范大学浙江省

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 基本概念
    1.3 本文主要结果
第二章 3-色图的单色连通数
    2.1 基本定义与引理
    2.2 主要结果
第三章 r-部图的单色连通数
    3.1 基本定义与引理
    3.2 上界1
    3.3 上界2
第四章 图的单色连通数达到上界的充分必要性
    4.1 基本定义与引理
    4.2 图G的单色连通数达到上界m-n-χ（G）
    4.3 图G的单色连通数达到上界m-n+χ（G）-1
参考文献
攻读学位期间取得的研究成果
致谢



本文编号：3041768