最大次数为3的色指数临界图的一种构造

摘要

G的k-(边)着色是一个映射π:E(G)→{1,2,…,k},使得G的相邻边没有相同的象.图G的色指数x'(G)=min{k| G有一个k-着色}.给出了最大次数为3的图的5种类型的四边形扩张变换,证明了这5种类型的变换保持图的临界性不变,并可利用这种变换构造出阶数较高的新的临界图.%The chromatic indeχ'( G) of a graph G was the minimum number of colors required to color the edges of G so that different colors were received for two adjacent edges. Five quadrangle extension types of graphs of maximum degree 3 were given and the stable criticality of them was proved. Furthermore , it could be used to construct new critical graphs in higher color levels.