论文部分内容阅读
无环图G的一个边着色π是从边集E到颜色集C的一个映射π：E→C，使得G中任何两条相邻的边均有不同的像。若|C|=k，则称π是G的一个k-边着色。使得G有k-边着色的最小k值称为G的边色数，即：x(G)=min{k|G存在一个k-边着色}。著名的Vizing定理表明：若G是简单图，则x(G)≤△+1。根据边着色的定义可知x(G)≥△。于是人们根据图的边色数将简单图分为两类，即若x(G)=△，则称G是第一类图；若x(G)=△+1，则称G是第二类图。设G是连通第二类图，且对G的任何边e都有：x(G-e)＜x(G)，则称G是临界图。本文根据临界图的定义和VAL定理讨论了△≥5的临界图的若干性质，为冲击临界图猜想作了准备工作。 图G的一个顶点着色φ是从顶点集V到颜色集C的一个映射φ：V→C，使得G中任何两个相邻的顶点均无相同的像。若|C|=k，则称φ是G的一个k-顶点着色。使得G有k-顶点着色的最小k值称为G的顶点色数，用x(G)表示。 设I(G)={(v，e)|v∈V，e∈E且v与e相关联}是G的关联集。称G的两个关联(v，e)和(w，f)相邻当且仅当下列三种情况之一成立：(1)v=w；(2)e=f；(3)vw=e或vw=f。图G的一个关联着色σ是从关联集I(G)到颜色集c的一个映射σ：I(G)→C，使得I(G)中任何两个相邻的关联都有不同的像。若σ：I(G)→C是G的一个关联着色且|C|=k，则称G是k-可关联着色的。使得G有k-可关联着色的最小k值称为G的关联色数，用x_i(G)表示。 本文根据关联着色和顶点着色的定义、性质给出了关联图的两个等价定义，并在此基础上讨论了关联图的一些性质以及关联着色与顶点着色的若干关系；利用穷染法和换色技巧确定了Merediths图的关联色数；从图的结构性质出发，利用双重归纳法和换色技巧证明了△≥4的系列平行图都存在一个(△+2，2)-关联着色；根据(k，l)-关联着色的定义和△=4，mad(G)＜3的图的结构性质，利用归纳法和换色技巧证明了△=4，mad(G)＜3的图G存在一个(6，2)-关联着色。