论文部分内容阅读
设G是一个图,C是G上的一个边着色,则我们称G是一个边染色图。对于G中的一个圈,如果它所有边的颜色都各不相同,则称这个圈为异色圈。设υ是G中的一点,它的色邻域CN(υ)定义为集合.{C(e):e在G中与υ关联},它的色度定义为d(υ)=|CN(υ)|。在色度条件下,Li和Wang得到了一些关于异色圈存在性问题的结果。
在这篇论文中,我们的目的是研究异色圈存在问题的色邻域并条件。我们给出了上面提到色邻域并条件下的那个性质的另外两个证明而且将之推广到一般情形,证明了:如果对于染色图G中的每对点υ,υ都有|CN(υ)∪CN(υ)|≥n-p,那么当n≥p(p+1)/2+2时G中至少存在一个异色三角形或异色四边形。
本论文的结构如下:第一章,回顾图论的基础知识和相关概念和符号的定义;第二章,介绍异色圈的背景知识和相关结果;第三章,首先介绍几个对于我们的研究非常重要的结果,然后给出本文的主要结果和完整证明,最后介绍一些有待解决的猜想。