论文部分内容阅读
边染色图的结构研究是图论研究的前沿课题之一.边染色图的连通性作为其中问题之一,发展十分迅速.图的单色连通性是一个近年来逐渐活跃起来的新兴问题.单色连通的概念是Caro和Yuster在2011年提出来的,它指的是在连通图G中任意两个点之间都是由单色路径连通.单色连通染色(简称MC-染色)是指图G的一个边染色使得图G单色连通.对于一个连通图G,单色连通数mc(G)指的是使得图G是MC-染色所允许的最大颜色数.很显然,对于任意的连通图G我们都有一个直观的下界 mc(G)≥|E(G)|-|V(G)|+2.研究者们也给出了若干上界和达到下界的限制条件.其中,Caro和Yuster证明了无三角形和直径大于等于3的连通图达到此下界,同时还给出了与色数相关的上界;Jin等人找到了更多的图类达到此下界同时也给出了若干上界.本文主要研究达到单色连通数下界的若干充分性条件,以及找出满足下界的一些图类.以下是本论文的主要结构和研究内容.在第一章中,主要介绍了本论文所涉及的图论基本概念和术语,对单色连通问题的研究背景和研究现状进行详细阐述,并简要叙述了本学位论文的主要结果.在第二章中,主要对现有的结论做了进一步的推广,证明了无沙漏图并三角形的图和无(?)的图的单色连通数刚好满足下界;同时证明了直径为2的极小连通图的单色连通数达到下界.在第三章中,主要研究含有K4的图在什么条件下能满足下界,我们证明当图G中含有同构于K4的子图且这任意的两个K4子图都是点不交或者边不交时,图的单色连通数满足下界.在第四章中,主要研究在什么条件下含有K1+P4的图能满足下界,我们证明当图G中含有同构于K1+P4的子图且这任意的两子图都点不交时,图的单色连通数满足下界.在第五章中,主要考虑当满足何种条件时含有鱼图的图G能达到下界,我们证明了当图G中的鱼图两两点不交时,图G的单色连通数满足下界.