完全图的强边着色  

The Strong Edge Colourings of Complete Graphs

作　　者：连广昌[1] 连翔[1] 

机构地区：[1]金陵科技学院基础课教学部,江苏南京210001

出　　处：《金陵科技学院学报》2007年第3期1-4,共4页Journal of Jinling Institute of Technology

摘　　要：如果图G有一个合理边着色,且图G中所有顶点上的关联边着色集合都互不相同,则这种合理边着色又称为图G的强边着色。具有强边着色的图称为图G的强边着色图。使图G有强边着色的最小色数称为图G的强边色数。本文利用强边着色矩阵,讨论了完全图的强边着色及其分类,证明了:当n是奇数时,图Kn是一个第二类强边着色图,且χs′(Kn)=Δ(Kn)+1;当n是偶数时,图Kn是一个第三类强边着色图,且χs′(Kn)=Δ(Kn)+2。或者,χs′(Kn)=3+2[(n-2)/2],这里[x]表示取小于、等于x的最大整数。If a graph G has a proper edge colourings such that the incident edge colourings sets between any two vertices in the graph G are different from each other, then such an edge colourings is said to be a strong edge colourings of graph G. The graph with a strong edge colourings is said to be the strong edge colourings graph. The minimum chromatic number to guarantee that the graph G has a strong edge colourings, is said to be the strong edge chromatic number of graph G. This paper uses the strong edge colourings matrix to discuss the strong edge colourings of complete graph and its classification, and proves that when n is odd, the graph K,, is the secondary class strong edge colourings graph and Х＇s（Kn） = A（Kn ） ＋ 1; and when n is even, the graph K, is the third class strong edge colourings graph and Х＇s（Kn）=△（Kn）＋2 .Or,Х＇s（Kn）=3＋2[n-2/2], here [x] expresses the maximum integer of ＂≤x ＂.

关 键 词：完全图 强边着色矩阵 强边着色 强边色数 分类 

分 类 号：O157.5[理学—数学]